Dva grafy - Two-graph
v matematika, a dva grafy je sada (neuspořádaných) trojic vybraných z konečné sada vrcholů X, takže každý (neuspořádaný) čtyřnásobek z X obsahuje sudý počet trojic dvou grafů. A pravidelný two-graph has the property that every pair of vertices lies in the same number of triples of the two-graph. Dva grafy byly studovány kvůli jejich spojení s rovnoramenné čáry a pro běžné dva grafy silně pravidelné grafy, a také konečné skupiny protože mnoho běžných dvou grafů je zajímavých automorfické skupiny.
Dva grafy nejsou grafy a neměly by být zaměňovány s jinými nazývanými objekty 2-grafy v teorie grafů, jako 2 pravidelné grafy.
Příklady
Na množině vrcholů {1, ..., 6} je následující kolekce neuspořádaných trojic dvou grafů:
- 123 124 135 146 156 236 245 256 345 346
Tento dva graf je pravidelný dva grafy, protože každá dvojice odlišných vrcholů se objevuje společně přesně ve dvou trojicích.
Vzhledem k jednoduchému grafu G = (PROTI,E), množina trojic vrcholové množiny PROTI jehož indukovaný podgraf má lichý počet hran, tvoří na množině dva grafy PROTI. Takto lze znázornit každý dva grafy.[1] Tento příklad se označuje jako standardní konstrukce dvou grafu z jednoduchého grafu.
Jako složitější příklad pojďme T být strom se sadou hran E. Sada všech trojic E které nejsou obsaženy v cestě T tvoří na sestavě dva grafy E.[2]
Přepínání a grafy
Dva grafy jsou ekvivalentem přepínací třídy grafů a také (přepsané) přepínací třídy podepsané kompletní grafy.
Přepínání množina vrcholů v (jednoduchém) grafu znamená obrácení sousedství každé dvojice vrcholů, jeden v množině a druhý ne v množině: tím se změní hranová množina tak, že sousední pár se stane nesousedícím a nesousedící pár se stane přilehlý. Okraje, jejichž koncové body jsou v sadě nebo oba nejsou v sadě, se nezmění. Grafy jsou přepínací ekvivalent pokud lze jeden získat od druhého přepnutím. Třída ekvivalence grafů při přepínání se nazývá a přepínací třída. Přepínání bylo zavedeno van Lint & Seidel (1966) a vyvinutý Seidelem; bylo voláno přepínání grafů nebo Přepínání Seidel, částečně pro odlišení od přepínání podepsané grafy.
Ve standardní konstrukci dvou grafů z jednoduchého grafu uvedeného výše poskytnou dva grafy stejný dva grafy právě tehdy, pokud jsou ekvivalentní při přepínání, to znamená, že jsou ve stejné přepínací třídě.
Nechť Γ je dvojitý graf na množině X. Pro jakýkoli prvek X z X, definujte graf se sadou vrcholů X s vrcholy y a z sousedící, právě když {X, y, z} je v Γ. V tomto grafu X bude izolovaný vrchol. Tato konstrukce je reverzibilní; daný jednoduchý graf G, připojit nový prvek X na množinu vrcholů G a definujte dva grafy, jejichž trojice jsou všechny {X, y, z} kde y a z jsou sousední vrcholy v G. Tento dvougraf se nazývá rozšíření z G podle X v teoretický jazyk designu.[3] V dané přepínací třídě grafů běžného dvou grafu nechť ΓX být jedinečný graf, který má X jako izolovaný vrchol (to vždy existuje, stačí vzít libovolný graf ve třídě a přepnout otevřené okolí X) bez vrcholu X. To znamená, že dva grafy jsou příponou ΓX podle X. V prvním příkladu výše pravidelného dvou grafu ΓX je 5-cyklus pro jakýkoli výběr X.[4]
Do grafu G odpovídá podepsaný kompletní graf Σ na stejné množině vrcholů, jehož hrany jsou podepsány záporně, pokud jsou v G a pozitivní, pokud není v G. Naopak, G je podgraf Σ, který se skládá ze všech vrcholů a všech záporných hran. Dva grafy G lze také definovat jako množinu trojic vrcholů, které podporují záporný trojúhelník (trojúhelník s lichým počtem záporných hran) v Σ. Dva podepsané kompletní grafy přinášejí stejný dva grafy právě tehdy, když jsou ekvivalentní při přepínání.
Přepínání G a Σ souvisí: přepínáním stejných vrcholů v obou se získá graf H a jeho odpovídající podepsaný kompletní graf.
Matice sousedství
The matice sousedství dvou grafu je matice sousedství příslušného podepsaného úplného grafu; tak to je symetrický, je na diagonále nula a má hodnoty ± 1 mimo úhlopříčku. Li G je graf odpovídající podepsanému úplnému grafu Σ, tato matice se nazývá (0, -1, 1) matice náhodnosti nebo Seidelská matice sousedství z G. Matice Seidel má na hlavní úhlopříčce nulové položky, -1 položky pro sousední vrcholy a +1 položky pro nesousedící vrcholy.
Pokud grafy G a H jsou ve stejné přepínací třídě, multisety vlastních čísel obou Seidelské matice sousedství z G a H shodovat, protože matice jsou podobné.[5]
Dva grafy na množině PROTI je pravidelný právě tehdy, má-li jeho matice sousedství jen dva odlišné vlastní čísla ρ1 > 0> ρ2 řekněme, kde ρ1ρ2 = 1 - |PROTI|.[6]
Rovnoúhlé čáry
Každý dva grafy jsou ekvivalentní množině čar v některých dimenzionálních euklidovský prostor každá dvojice se setkává ve stejném úhlu. Sada řádků vytvořených ze dvou grafů n vrcholy se získají následovně. Nechť -ρ je nejmenší vlastní číslo z Seidelská matice sousedství, A, dvou grafu, a předpokládejme, že má multiplicitu n - d. Pak matice ρJá + A je kladný polořadovka definitivní hodnosti d a tedy může být reprezentován jako Gramová matice vnitřních výrobků z n vektory v euklidovštině d-prostor. Protože tyto vektory mají stejné norma (a to, ) a vzájemné vnitřní produkty ± 1, libovolný pár n nimi překlenuté čáry se setkávají ve stejném úhlu φ, kde cos φ = 1 / ρ. Naopak, jakákoli sada neortogonálních rovnoramenných čar v euklidovském prostoru může vést ke vzniku dvou grafů (viz rovnoramenné čáry pro stavbu).[7]
S výše uvedeným zápisem je maximální mohutnost n splňuje n ≤ d(ρ2 - 1) / (ρ2 - d) a hranice je dosažena tehdy a jen tehdy, je-li dvou-graf pravidelný.
Silně pravidelné grafy
Dva grafy na X skládající se ze všech možných trojic X a žádné trojnásobky X jsou pravidelné dva grafy a jsou považovány za triviální dva grafy.
Pro netriviální dva grafy v sadě X, dva grafy jsou pravidelné právě tehdy, když pro některé X v X graf ΓX je silně pravidelný graf s k = 2μ (stupeň kteréhokoli vrcholu je dvojnásobkem počtu vrcholů sousedících s oběma nesousedícími páry vrcholů). Pokud tato podmínka platí pro jednu X v X, platí pro všechny prvky X.[8]
Z toho vyplývá, že netriviální pravidelný dvougraf má sudý počet bodů.
Li G je běžný graf, jehož rozšíření o dva grafy má n body, pak Γ je běžný dvougraf, pokud a pouze pokud G je silně pravidelný graf s vlastními hodnotami k, r a s uspokojující n = 2(k - r) nebo n = 2(k - s).[9]
Poznámky
- ^ Colburn & Dinitz 2007, str. 876, poznámka 13.2
- ^ Cameron, P. J. (1994), „Dva grafy a stromy“, Diskrétní matematika, 127: 63–74, doi:10.1016 / 0012-365x (92) 00468-7 citováno v Colburn & Dinitz 2007, str. 876, Stavba 13.12
- ^ Cameron & van Lint 1991, str. 58-59
- ^ Cameron & van Lint 1991, str. 62
- ^ Cameron & van Lint 1991, str. 61
- ^ Colburn & Dinitz 2007, str. 878 # 13.24
- ^ van Lint & Seidel 1966
- ^ Cameron & van Lint 1991, str. 62 Věta 4.11
- ^ Cameron & van Lint 1991, str. 62 Věta 4.12
Reference
- Brouwer, A.E. Cohen, A.M. a Neumaier, A. (1989), Vzdálené pravidelné grafy. Springer-Verlag, Berlín. Sekce 1.5, 3.8, 7.6C.
- Cameron, P.J .; van Lint, J.H. (1991), Vzory, grafy, kódy a jejich odkazy, London Mathematical Society Student Texts 22, Cambridge University Press, ISBN 978-0-521-42385-4
- Colbourn, Charles J; Corneil, Derek G. (1980). Msgstr "Při rozhodování o přepínání ekvivalence grafů". Disk. Appl. Matematika. 2 (3): 181–184. doi:10.1016 / 0166-218X (80) 90038-4.
- Colbourn, Charles J .; Dinitz, Jeffrey H. (2007), Příručka kombinatorických vzorů (2. vyd.), Boca Raton: Chapman & Hall / CRC, str.875–882, ISBN 1-58488-506-8
- Godsil, Chris: Royle, Gordone (2001), Algebraická teorie grafů. Postgraduální texty z matematiky, sv. 207. Springer-Verlag, New York. Kapitola 11.
- Mallows, C. L .; Sloane, N. J. A. (1975). "Dva grafy, přepínací třídy a Eulerovy grafy mají stejný počet". SIAM J. Appl. Matematika. 28 (4): 876–880. CiteSeerX 10.1.1.646.5464. JSTOR 2100368.
- Seidel, J. J. (1976), Průzkum dvou grafů. V: Colloquio Internazionale sulle Teorie Combinatorie (Proceedings, Rome, 1973), sv. I, str. 481–511. Atti dei Convegni Lincei, č. 17. Accademia Nazionale dei Lincei, Řím. Přetištěno v Seidel (1991), str. 146–176.
- Seidel, J. J. (1991), Geometry and Combinatorics: Selected Works of J.J. Seidele, vyd. D. G. Corneil a R. Mathon. Academic Press, Boston, 1991.
- Taylor, D. E. (1977), pravidelné 2-grafy. Proceedings of the London Mathematical Society (3), sv. 35, s. 257–274.
- van Lint, J. H .; Seidel, J. J. (1966), "Rovnostranné bodové sady v eliptické geometrii", Indagationes Mathematicae, Proc. Koninkl. Ned. Akad. Wetenschap. Ser. A 69, 28: 335–348