Slovně reprezentovatelný graf - Word-representable graph

V matematické oblasti teorie grafů, a slovně reprezentovatelný graf je graf které lze charakterizovat slovem (nebo posloupností), jehož záznamy se předepsaným způsobem střídají. Zejména pokud je vrcholová sada grafu PROTI, člověk by měl být schopen vybrat si slovo w přes abecedu PROTI takové dopisy A a b střídat se w jen a jen v případě, že dvojice ab je hrana v grafu. (Písmena A a b střídat v w pokud po vyjmutí z w všechna písmena kromě kopií A a b, jeden dostane slovo abab... nebo slovo babaNapříklad) graf cyklu označeno A, b, C a d ve směru hodinových ručiček je reprezentovatelný slovem, protože jej lze vyjádřit pomocí abdacdbc: páry ab, před naším letopočtem, CD a inzerát střídat, ale páry ac a bd ne.

Slovo w je Gje zástupce slovaa jeden říká, že to w představuje G. Nejmenší (podle počtu vrcholů) neslovně reprezentovatelný graf je graf kola Ž₅, což je jediný non-word-reprezentovatelný graf na 6 vrcholech.

Definice grafu reprezentovatelného slovem funguje v označených i neoznačených případech, protože jakékoli označení grafu je ekvivalentní jakémukoli jinému označení. Třída slovně reprezentovatelných grafů také je dědičný. Slovně reprezentovatelné grafy zobecňují několik důležitých tříd grafů, jako např kruhové grafy, 3barevné grafy a srovnatelné grafy. Různé zevšeobecnění teorie slovně reprezentovatelných grafů pojme reprezentaci žádný graf.

Dějiny

Slovně reprezentovatelné grafy představil Sergej Kitaev v roce 2004 na základě společného výzkumu se Stevenem Seifem^[1] na Perkinsova poloskupina, který hraje důležitou roli v teorii semigroup od roku 1960.^[2] První systematické studium slovně reprezentovatelných grafů provedli v roce 2008 Kitaev a Artem Pyatkin,^[3] zahájení vývoje teorie. Jedním z klíčových přispěvatelů do této oblasti je Magnús M. Halldórsson^[4][5][6]. Doposud bylo na téma a jádro knihy napsáno více než 35 prací^[2] Sergey Kitaev a Vadim Lozin se věnuje teorii grafů reprezentovatelných slovem. Rychlým způsobem, jak se s touto oblastí seznámit, je přečíst si jeden z článků průzkumu^[7][8][9].

Motivace ke studiu grafů

Podle ^[2], slovně reprezentovatelné grafy jsou relevantní pro různé obory, což poskytuje motivaci ke studiu grafů. Tato pole jsou algebra, teorie grafů, počítačová věda, kombinatorika slov, a plánování. Slova reprezentovatelné grafy jsou v teorii grafů obzvláště důležité, protože zobecňují několik důležitých tříd grafů, např. kruhové grafy, 3barevné grafy a srovnatelné grafy.

Časné výsledky

Bylo ukázáno v ^[3] že graf G je reprezentovatelný slovem, pokud je k-reprezentativní pro některé k, to znamená, G může být reprezentován slovem majícím k kopie každého dopisu. Navíc, pokud je graf k-reprezentativní pak je také (k + 1) - reprezentativní. Pojem reprezentační číslo grafujako minimální k takže graf je reprezentovatelný slovem, je dobře definovaný. Grafy, které nelze reprezentovat slovy, mají reprezentační číslo ∞. Grafy s reprezentací číslo 1 jsou přesně sadou kompletní grafy, zatímco grafy s reprezentací číslo 2 jsou přesně třídou kruh neúplné grafy. Zejména, lesy (kromě single stromy na maximálně 2 vrcholech), žebříkové grafy a cyklické grafy mít reprezentaci číslo 2. Klasifikace grafů s reprezentací číslo 3 není známa. Existují však příklady takových grafů, např. Petersenův graf a hranoly. Navíc 3pododdělení libovolného grafu je 3 reprezentovatelný. Zejména pro každý graf G existuje 3 reprezentativní graf H který obsahuje G jako Méně důležitý ^[3].

Graf G je permutačně reprezentativní jestliže to může být reprezentováno slovem formuláře p₁p₂...p_k, kde p_i je permutace. On to také může říct G je permutačně k-zastupitelný. Graf je permutačně reprezentovatelný, pokud je a srovnávací graf ^[1]. Graf, který je reprezentovatelný slovem, znamená, že sousedství každého vrcholu je permutačně reprezentovatelný (tj. je a srovnávací graf ) ^[1]. Převod na poslední výrok není pravdivý ^[4]. Nicméně skutečnost, že sousedství každého vrcholu je a srovnávací graf znamená, že Maximum Clique problém je polynomiálně řešitelný na grafech reprezentovatelných slovem ^{[5] [6]}.

Semi-tranzitivní orientace

Semi-tranzitivní orientace poskytuje mocný nástroj ke studiu grafů reprezentovatelných slovem. Směrovaný graf je semi-tranzitivně orientovaný pokud ano acyklický a pro jakoukoli směrovanou cestu u₁→u₂→ ...→u_t, t ≥ 2, buď není hrana z u₁ na u_t nebo všechny hrany u_i → u_j existují pro 1 ≤ i < j ≤ t. Klíčová věta v teorii grafů reprezentovatelných slovem uvádí, že graf je reprezentovatelný slovem, pokud připouští semi-tranzitivní orientaci ^[6]. Jako důsledek důkazu klíčové věty se získá horní hranice slovních zástupců: Každý neúplný slovně reprezentovatelný graf G je 2 (n − κ(G)) - reprezentativní, kde κ(G) je velikost maximální kliky v G ^[6]. Okamžitým důsledkem posledního prohlášení je, že problém s rozpoznáním reprezentace slov je v NP. V roce 2014 Vincent Limouzy poznamenal, že se jedná o NP-úplný problém rozpoznat, zda je daný graf reprezentovatelný slovem ^{[2] [7]}. Další důležitý důsledek klíčové věty je, že jakýkoli 3barevný graf je reprezentovatelný slovem. Poslední skutečnost naznačuje, že mnoho klasických problémů s grafy je u NP reprezentovatelných grafů obtížné.

Přehled vybraných výsledků

Non-word-representable graphs

Grafy kol Ž_2n+1, pro n ≥ 2, nejsou reprezentovatelné slovem a Ž₅ je minimální (podle počtu vrcholů) graf, který nelze reprezentovat slovy. Vezmeme-li jakýkoli graf nesrovnatelnosti a přidáme vrchol (vrchol spojený s jakýmkoli jiným vrcholem), získáme graf, který nelze reprezentovat slovy, který pak může vytvořit nekonečně mnoho grafů, které nelze reprezentovat ^[2]. Jakýkoli takto vytvořený graf bude nutně mít trojúhelník (cyklus délky 3) a vrchol stupně nejméně 5. Existují grafy, které nelze vyjádřit slovem, maximálního stupně 4 ^[10] a existují grafy bez trojúhelníků, které nelze reprezentovat slovy ^[5]. Existují také pravidelné neslovné reprezentativní grafy ^[2]. Neizomorfní spojitelné grafy, které nelze vyjádřit slovem, nejvýše na osmi vrcholech nejprve vyčíslil Heman Z.Q. Chen. Jeho výpočty byly rozšířeny ^[11], kde bylo ukázáno, že počty neizomorfních neslovně reprezentovatelných spojených grafů na 5−11 vrcholech jsou dány 0, 1, 25, 929, 54957, 4880093, 650856040. Toto je posloupnost A290814 v the Online encyklopedie celočíselných sekvencí (OEIS).

Operace s grafy a reprezentovatelnost slov

Operace zachovávající reprezentativnost slov jsou odstranění vrcholu, nahrazení vrcholu modulem, kartézský součin, kořenový součin, dělení grafu, spojení dvou grafů hranou a slepení dvou grafů ve vrcholu ^[2]. Operace, které nutně nezachovávají reprezentaci slov, berou doplněk, berou spojnicový graf, kontrakci hran ^[2], lepením dvou grafů do kliky velikosti 2 nebo více ^[12], tenzorový produkt, lexikografický produkt a silný produkt ^[13]. Odstranění okraje, přidání okraje a zvednutí okraje s ohledem na reprezentativnost slov (ekvivalentně, semi-tranzitivní orientovatelnost) jsou studovány v ^[13].

Grafy s vysokým počtem reprezentací

Zatímco každý neúplný slovně reprezentativní graf G je 2 (n − κ(G)) - reprezentativní, kde κ(G) je velikost maximální kliky v G ^[6], nejvyšší známé číslo zastoupení je podlaha (n/ 2) dané korunové grafy s úplně sousedícím vrcholem ^[6]. Zajímavé je, že takové grafy nejsou jedinými grafy, které vyžadují dlouhou reprezentaci ^[14]. Ukázalo se, že samotné korunové grafy vyžadují mezi bipartitními grafy dlouhé (možná nejdelší) reprezentace ^[15].

Výpočetní složitost

Známé výpočetní složitosti problémů na slovně reprezentovatelných grafech lze shrnout následovně ^{[2] [7]}:

Reprezentace rovinných grafů

Bez trojúhelníků rovinné grafy jsou reprezentovatelné slovem ^[6]. Blízká triangulace bez K4 je 3-barevná, právě když je reprezentovatelná slovem ^[16]; tento výsledek zobecňuje studie v ^[17][18]. Je studována slovní reprezentovatelnost dělení ploch trojúhelníkových mřížkových grafů ^[19] a je studována slovní reprezentovatelnost triangulací mřížkových válcových grafů ^[20].

Reprezentace dělených grafů

Slovní reprezentace rozdělené grafy je studován v ^[21][12]. Zejména, ^[21] nabízí charakterizaci ve smyslu zakázaných indukovaných podgrafů slovně reprezentovatelných rozdělených grafů, ve kterých vrcholy v nezávislé sadě mají stupeň maximálně 2, nebo velikost kliky je 4, zatímco výpočetní charakterizace slovně reprezentovatelných dělených grafů s klika o velikosti 5 je uvedena v ^[12]. Rovněž jsou uvedeny nezbytné a dostatečné podmínky pro to, aby orientace děleného grafu byla semi-tranzitivní ^[21], zatímco v ^[12] prahové grafy jsou znázorněny jako slovně reprezentovatelné a rozdělené grafy slouží k ukázce, že slepení dvou slovně reprezentovatelných grafů do jakékoli kliky o velikosti alespoň 2 může, ale nemusí vést ke slovně reprezentovatelnému grafu, který vyřešil dlouhodobě otevřený problém.

Grafy reprezentovatelné vzorem vyhýbajícím se slovům

Graf je p-zastupitelný jestliže to může být reprezentováno slovem vyhýbat se a vzor p. Například 132 reprezentovatelných grafů jsou ty, které lze reprezentovat slovy w₁w₂...w_n kde nejsou 1 ≤ A < b < C ≤ n takhle w_A < w_C < w_b. v ^[22] je ukázáno, že jakýkoli 132 reprezentovatelný graf je nutně a kruhový graf a jakékoli strom a jakékoli graf cyklu, stejně jako jakýkoli graf na maximálně 5 vrcholech, lze zobrazit 132. Bylo ukázáno v ^[23] že ne všechny kruhové grafy jsou reprezentovatelné 132 a že 123-reprezentovatelné grafy jsou také vhodnou podtřídou třídy kruhových grafů.

Zobecnění

Řada zobecnění ^[24][25][26] pojmu slovně reprezentovatelného grafu jsou založeny na pozorování pomocí Jeff Remmel že ne-hrany jsou definovány výskytem vzoru 11 (dvě po sobě jdoucí stejná písmena) ve slově představujícím graf, zatímco hrany jsou definovány vyloučením tohoto vzoru. Například namísto vzoru 11 lze použít vzor 112 nebo vzor 1212 nebo jakýkoli jiný binární vzor, ​​kde lze vytvořit předpoklad, že je uspořádána abeceda, takže písmeno ve slově odpovídající 1 v vzor je menší než ten, který odpovídá 2 ve vzoru. Pronájem u být uspořádaným binárním vzorem, dostaneme představu a u-reprezentativní graf. Slovně reprezentovatelné grafy jsou tedy jen třídou 11 reprezentovatelných grafů. Zajímavé je, jakýkoli graf může být u-zastoupeny za předpokladu u má délku nejméně 3 ^[27].

Další způsob, jak zobecnit pojem slovně reprezentovatelného grafu, opět navrhl Jeff Remmel, je zavést „stupeň tolerance“ k pro výskyty vzoru p definování hran / ne-hran. To znamená, že můžeme říci, že pokud existují až k výskyt p tvořené písmeny A a b, pak je mezi nimi hrana A a b. To dává představu o k-p- reprezentativní graf a kStudováno je 11 grafů ^[28]. Všimněte si, že 0-11 reprezentovatelné grafy jsou přesně grafy reprezentovatelné slovem. Klíčové výsledky v ^[28] to je žádný graf je reprezentovatelný 2-11 a že grafy reprezentovatelné slovem jsou správnou podtřídou grafů reprezentovatelných 1-11. Zda je či není libovolný graf reprezentovatelný pro 1-11, je náročný otevřený problém.

Pro další typ příslušného zobecnění, Hans Zantema navrhl představu o k-semi-tranzitivní orientace upřesnění pojmu semitranzitivní orientace ^[14]. Myšlenka zde se omezuje na uvažování pouze směrované dráhy o délce nepřesahující k a zároveň umožňuje narušení semi-tranzitivity na delších cestách.

Otevřené problémy

Otevřené problémy na slovně reprezentovatelných grafech najdete v ^{[2] [7] [8] [9]}a zahrnují:

• Charakterizujte (ne) slovně reprezentovatelné rovinné grafy.
• Charakterizujte slovem reprezentovatelné blízké triangulace obsahující celý graf K.₄ (taková charakterizace je známá pro K.₄-planární grafy zdarma ^[16]).
• Klasifikujte grafy podle čísla 3. (Viz ^[29] pro nejmodernější v tomto směru.)
• Je hranový graf non-word-representable graph always non-word-representable?
• Existují nějaké grafy n vrcholy, jejichž zobrazení vyžaduje více než podlahu (n/ 2) kopie každého dopisu?
• Je to pravda ze všeho bipartitní grafy korunové grafy vyžadovat nejdelší slovní zástupce? (Vidět ^[15] pro příslušnou diskusi.)
• Charakterizujte grafy reprezentovatelné slovy z hlediska (indukovaných) zakázaných podgrafů.
• Které (tvrdé) problémy v grafech lze přeložit na slova, která je reprezentují, a řešit je na slovech (efektivně)?

Literatura

Seznam publikací ke studiu zastoupení grafů slovy obsahuje, ale není omezen na

1. Ó. Akgün, I.P. Gent, S. Kitaev, H. Zantema. Řešení výpočtových problémů v teorii slovně reprezentovatelných grafů. Journal of Integer Sequences 22 (2019), článek 19.2.5.
2. P. Akrobotu, S. Kitaev a Z. Masárová. O slovní reprezentovatelnosti polyomino triangulací. Sibiřský Adv. Matematika. 25 (2015), 1-10.
3. B. Broere. Word representable graphs, 2018. Diplomová práce na Radboud University v Nijmegenu.
4. B. Broere a H. Zantema. „The k-krychle je k- reprezentativní, „J. Autom., Lang. a Combin. 24 (2019) 1, 3-12.
5. J. N. Chen a S. Kitaev. Na 12-reprezentativnosti indukovaných podgrafů mřížkového grafu, Discussiones Mathematicae Graph Theory, to appear
6. T. Z. Q. Chen, S. Kitaev a A. Saito. Reprezentující rozdělené grafy slovy, arXiv: 1909.09471
7. T. Z. Q. Chen, S. Kitaev a B. Y. Sun. Reprezentovatelnost slov dělení ploch trojúhelníkových mřížkových grafů, grafů a kombinací. 32 (5) (2016), 1749-1761.
8. T. Z. Q. Chen, S. Kitaev a B. Y. Sun. Slovní reprezentovatelnost triangulací mřížkových válcových grafů, Discr. Appl. Matematika. 213 (2016), 60-70.
9. G.-S. Cheon, J. Kim, M. Kim a S. Kitaev. Reprezentativnost Toeplitzových grafů, Discr. Appl. Math., Aby se objevil.
10. G.-S. Cheon, J. Kim, M. Kim a A. Pyatkin. Na k-11-reprezentovatelné grafy. J. Combin. 10 (2019) 3, 491−513.
11. I. Choi, J. Kim a M. Kim. O operacích zachovávajících semi-tranzitivní orientační schopnost grafů, Journal of Combinatorial Optimization 37 (2019) 4, 1351−1366.
12. A. Collins, S. Kitaev a V. Lozin. Nové výsledky v grafech reprezentovatelných slovem, Discr. Appl. Matematika. 216 (2017), 136-141.
13. A. Daigavane, M. Singh, B.K. Jiří. 2 uniformní slova: cyklické grafy a algoritmus k ověření konkrétních slovních reprezentací grafů. arXiv: 1806.04673 (2018).
14. M. Gaetz a C. Ji. Výčet a rozšíření slovně reprezentovatelných grafů. Přednášky v informatice 11682 (2019) 180−192. In R. Mercas, D. Reidenbach (Eds) Combinatorics on Words. SLOVA 2019.
15. M. Gaetz a C. Ji. Výčet a rozšíření zástupců Word, arXiv: 1909 00019.
16. M. Gaetz a C. Ji. Výčet a rozšíření zástupců slov, kombinatorika slov, 180-192, poznámky k přednášce ve výpočtu. Sci., 11682, Springer, Cham, 2019.
17. A. Gao, S. Kitaev a P. Zhang. Na 132 reprezentovatelných grafech. Australasian J. Combin. 69 (2017), 105-118.
18. M. Glen. Barevnost a reprezentovatelnost slov blízkých triangulací, Pure and Applied Mathematics, se objeví, 2019.
19. M. Glen. O reprezentaci slov polyomino triangulací a korunových grafů, 2019. Doktorská práce, University of Strathclyde.
20. M. Glen a S. Kitaev. Reprezentativnost slov trojúhelníků obdélníkového polyomina s jedinou dlaždicí domino, J. Combin.Math. Kombinovat. Comput. 100, 131–144, 2017.
21. M. Glen, S. Kitaev a A. Pyatkin. Na reprezentačním čísle korunového grafu je Discr. Appl. Matematika. 244, 2018, 89-93.
22. M.M. Halldórsson, S. Kitaev, A. Pyatkin Na reprezentativních grafech, semitransitivních orientacích a číslech reprezentací, arXiv: 0810.0310 (2008).
23. M.M. Halldórsson, S. Kitaev, A. Pyatkin (2010) Grafy zachycující střídání slov. In: Y. Gao, H. Lu, S. Seki, S. Yu (eds), Developments in Language Theory. DLT 2010. Lecture Notes Comp. Sci. 6224, Springer, 436−437.
24. M.M. Halldórsson, S. Kitaev, A. Pyatkin (2011) Alternativní grafy. In: P. Kolman, J. Kratochvíl (eds), Graph-Theoretic Concepts in Computer Science. WG 2011. Lecture Notes Comp. Sci. 6986, Springer, 191-202.
25. M. Halldórsson, S. Kitaev a A. Pyatkin. Semi-tranzitivní orientace a slovně reprezentovatelné grafy, Discr. Appl. Matematika. 201 (2016), 164−171.
26. M. Jones, S. Kitaev, A. Pyatkin a J. Remmel. Reprezentace grafů pomocí slov vyhýbajících se slovům, elektron. J. Combin. 22 (2), Res. Pap. P2.53, 1-20 (2015).
27. S. Kitaev. Na grafech s reprezentací číslo 3 J. Autom., Lang. a Combin. 18 (2013), 97-112.
28. S. Kitaev. Komplexní úvod do teorie slovně reprezentovatelných grafů. In: É. Charlier, J. Leroy, M. Rigo (eds), Vývoj v teorii jazyka. DLT 2017. Lecture Notes Comp. Sci. 10396, Springer, 36−67.
29. S. Kitaev. Existence u-reprezentace grafů, Journal of Graph Theory 85 (2017) 3, 661−668.
30. S. Kitaev, Y. Long, J. Ma, H. Wu. Reprezentovatelnost slov u dělených grafů, arXiv: 1709.09725 (2017).
31. S. Kitaev a V. Lozin. Slova a grafy, Springer, 2015. ISBN  978-3-319-25859-1.
32. S. Kitaev a A. Pyatkin. Na reprezentativních grafech J. Autom., Lang. a Combin. 13 (2008), 45-54.
33. S. Kitaev a A. Pyatkin. Slovně reprezentovatelné grafy: a Survey, Journal of Applied and Industrial Mathematics 12 (2) (2018) 278−296.
34. S. Kitaev a A. Pyatkin. O semi-tranzitivní orientovatelnosti grafů bez trojúhelníků, arXiv: 2003.06204v1.
35. S. Kitaev a A. Saito. O semi-tranzitivní orientovatelnosti Kneserových grafů a jejich doplňků se objeví diskrétní matematika.
36. S. Kitaev, P. Salimov, C. Severs a H. Úlfarsson (2011) O reprezentovatelnosti spojnicových grafů. In: G. Mauri, A. Leporati (eds), Vývoj v teorii jazyka. DLT 2011. Lecture Notes Comp. Sci. 6795, Springer, 478−479.
37. S. Kitaev a S. Seif. Slovní úloha Perkinsovy poloskupiny prostřednictvím směrovaných acyklických grafů, Order 25 (2008), 177−194.
38. E. Leloup. Grafy reprezentativních příspěvků par mot. Diplomová práce, Univerzita v Lutychu, 2019
39. Mandelshtam. V grafech, které lze reprezentovat slovy vyhýbajícími se vzorům, Discussiones Mathematicae Graph Theory 39 (2019) 375−389.
40. С. В. Китаев, А. В. Пяткин. Графы, представимые в виде слов. Обзор результатов, Дискретн. анализ и исслед. опер., 2018, том 25, номер 2, 19−53.

Software

Software pro studium grafů reprezentujících slovo najdete zde:

1. M. Glen. Software pro řešení grafů reprezentujících slovo, 2017. Dostupné na https://personal.cis.strath.ac.uk/sergey.kitaev/word-representable-graphs.html.
2. H. Zantema. Software REPRNR pro výpočet reprezentačního čísla grafu, 2018. Dostupné na https://www.win.tue.nl/~hzantema/reprnr.html.

Reference