Dvoupočet

V matematice je dvougraf (neuspořádaná) množina trojic vybraných z konečné množiny vrcholů X takovým způsobem, že jakákoliv (neuspořádaná) čtyřka v X obsahuje sudý počet zvolených trojic dvou grafů. V pravidelném (homogenním) dvougrafu leží libovolná dvojice vrcholů ve stejném počtu trojic dvougrafu. Dvougrafy jsou studovány pro jejich spojení s rovnoúhelnými čarami , spojení pravidelných dvougrafů se silně regulárními grafy a také pro spojení pravidelných dvougrafů s konečnými grupami , protože mnoho z těchto grafů má zajímavé skupiny automorfismu .

Dva grafy nejsou grafy a neměly by být zaměňovány s jinými objekty, které se v teorii grafů nazývají 2-grafy , zejména 2-regulární grafy . Pro rozlišení mezi nimi se používá slovo „dva“, nikoli číslice „2“ [1] .

Dvougrafy zavedl G. Higman jako přírodní objekty, které vznikají při práci s některými jednoduchými skupinami. Od té doby se jimi intenzivně zabývali Seidel, Taylor a další při studiu množin rovnoúhelníkových čar, silně pravidelných grafů a dalších objektů [2] [1] .

Příklady

Na množině vrcholů {1, ..., 6} je následující neuspořádaná množina trojic dvougraf:

123 124 135 146 156 236 245 256 345   346

Tento dvougraf je pravidelný, protože každá dvojice odlišných vrcholů skončí společně přesně ve dvou trojicích.

Je-li dán obyčejný graf G = ( V ,  E ), pak množina trojic vrcholů ve V , jejichž vygenerovaný podgraf má lichý počet hran, tvoří na V dvougraf . V této podobě lze znázornit libovolný dvougraf [3] . Tento příklad ukazuje standardní způsob vytvoření dvougrafu z normálního grafu.

Vezměme si složitější příklad. Nechť T je strom s množinou okrajů E . Množina všech trojic hran, které v T neleží na stejné dráze, tvoří na množině E dvojgraf . [4] [5]

Přepínání a grafy

Dvougraf je ekvivalentní třídě přepínání grafů, stejně jako třída přepínání (se znaménkem) úplných grafů se znaménkem .

Přepínání množiny vrcholů v (pravidelném) grafu znamená změnu sousednosti každé dvojice vrcholů, z nichž jeden je v množině a druhý v množině není - sousední dvojice se stane nesousedící a nesousedící dvojice sousedí. Hrany, jejichž koncové body jsou v sadě nebo oba koncové body jsou mimo sadu, se nemění. Grafy jsou ekvivalentní přepínání , pokud lze jeden získat od druhého přepínáním. Třída spínací ekvivalence se nazývá třída spínání . Přepínání zavedli van Lint a Seidel ( van Lint, Seidel 1966 ) a vyvinuli ho Seidel. Název přepínání grafů nebo přepínání Seidel byl zaveden, částečně, aby se odlišil od přepínání grafů se znaménkem .

Ve standardní konstrukci dvou grafů z běžného grafu uvedeného výše dávají dva grafy stejný dvougraf tehdy a pouze tehdy, pokud jsou ekvivalentní spínání, to znamená, že patří do stejné třídy spínání.

Nechť Γ je dvougraf na množině X . Pro libovolný prvek x z X definujeme graf množiny vrcholů X , ve kterém jsou vrcholy y a z sousední právě tehdy, když { x , y , z } patří do Γ. V tomto grafu bude x izolovaný vrchol. Tato konstrukce je reverzibilní. Dáme-li obyčejný graf G , přidejte nový prvek x do množiny vrcholů G a definujte dvougraf tak, aby všechny trojice { x , y , z } měly y a z sousední vrcholy v G . Tento dvougraf se v jazyce vývojových diagramů nazývá rozšíření grafu G o vrchol x . [1] V dané přepínací třídě běžného dvougrafu nechť je Γ x jediný graf, který má vrchol x jako izolovaný vrchol (jeden vždy existuje, stačí vzít libovolný graf ve třídě a přepnout relativně ne sousedních x vrcholů) a nezahrnuje samotný vrchol x . To znamená, že dvougraf je rozšířením Γ x o vrchol x . V běžném dvougrafovém příkladu je Γ x 5-vrcholový cyklus pro jakoukoli volbu x . [6]

Graf G odpovídá úplnému grafu Σ se znaménkem na téže množině vrcholů, jehož hrany jsou záporné, pokud patří do G , a kladné, pokud nepatří do G . Naopak G je podgraf Σ a skládá se ze všech vrcholů a záporných hran. Dvougraf G lze také definovat jako množinu trojic vrcholů, které tvoří záporný trojúhelník (trojúhelník s lichým počtem záporných hran) v Σ. Dva úplné grafy se znaménkem dávají stejný dvougraf tehdy a pouze tehdy, pokud jsou ekvivalentní.

Přepínání G a Σ jsou propojeny — přepnutím stejných vrcholů vznikne graf H a odpovídající úplný graf se znaménkem.

Matice sousedství

Matice sousednosti dvougrafu je maticí sousednosti odpovídajícího úplného grafu se znaménkem. To znamená, že je symetrický , na diagonále má nuly a hodnoty mimo úhlopříčku jsou ±1. Je-li G graf odpovídající úplnému grafu Σ se znaménkem, tato matice se nazývá (0, −1, 1) matice sousednosti nebo Seidelova matice sousednosti [ G . Seidelova matice má nuly na hlavní diagonále, −1 pro prvky odpovídající sousedním vrcholům a +1 pro prvky odpovídající nesousedícím vrcholům.

Pokud jsou grafy G a H ve stejné přepínací třídě, multimnožiny vlastních čísel dvou Seidelových matic sousednosti pro G a H se shodují, protože matice jsou podobné. [7]

Dvougraf na množině V je regulární právě tehdy, když má jeho matice sousedství pouze dvě odlišná vlastní čísla , řekněme ρ 1 > 0 > ρ 2 , kde ρ 1 ρ 2 = 1 − | V |. [osm]

Rovnoúhlé čáry

Jakýkoli dvougraf je ekvivalentní množině čar v nějakém vícerozměrném euklidovském prostoru a úhel mezi libovolným párem čar z této množiny je stejný. Množinu čar lze sestrojit ze dvou grafů s n vrcholy následovně. Nechť −ρ je nejmenší vlastní číslo Seidelovy matice sousedství A dvougrafu a předpokládejme, že jeho multiplicita je n  −  d . Potom je matice ρ I  +  A kladná semidefinitní matice řady d a lze ji reprezentovat jako Gramovu matici vnitřních součinů n vektorů v euklidovském prostoru dimenze d . Tyto vektory mají také stejnou normu (jmenovitě ) a párový skalární součin ±1 a úhel mezi libovolným párem n čar překlenutých těmito vektory je roven φ, kde cos φ = 1/ρ. Naopak každá množina neortogonálních čar v euklidovském prostoru, jejichž úhel mezi kteroukoli dvojicí je stejný, dává dvougraf [9] .

Ve výše uvedeném zápisu maximální mohutnost n splňuje nerovnost n ≤ d (ρ 2 − 1)/(ρ 2 − d ) a hranice je dosaženo právě tehdy, když je dvougraf pravidelný.

Silně pravidelné grafy

Dvougrafy na X sestávající ze všech možných trojic z X a prázdných (bez trojic) jsou běžné dvougrafy, ale obvykle jsou považovány za triviální dvojgrafy a jsou obvykle vyloučeny z úvahy.

Netriviální dvougraf na množině X je regulární právě tehdy, když pro libovolné x z X je graf Γ x silně regulární s k = 2μ (stupeň libovolného vrcholu je dvojnásobkem počtu vrcholů sousedících s oběma z libovolného nesousedícího páru z vrcholů). Pokud tato podmínka platí pro jedno x z X , pak platí pro všechny prvky z X . [deset]

To znamená, že netriviální pravidelný dvougraf má sudý počet vrcholů.

Jestliže G je regulární graf, jehož rozšířený dvougraf Γ má n vrcholů, pak Γ je regulérní dvougraf právě tehdy, když G je silně regulární graf s vlastními čísly k , r , as takovými, že n = 2 ( k  −  r ) nebo n = 2 ( k  −  s ). [jedenáct]

Poznámky

  1. ↑ 1 2 3 Cameron, van Lint, 1991 , str. 58-59.
  2. ↑ G. Eric Moorhouse. Dva grafy a šikmé dva grafy v konečných geometriích // Lineární algebra a její aplikace. — 1995.
  3. ↑ Colbourn, Dinitz, 2007 , str. 876, poznámka 13.2.
  4. ↑ P. J. Cameron. Dva grafy a stromy // Diskrétní matematika. - 1994. - T. 127 . - S. 63-74 . - doi : 10.1016/0012-365x(92)00468-7 . , jak je citováno v Colbourn a Dinitz, 2007 , s. 876, závěr 13.12.
  5. ↑ Peter J. Cameron. Počítání dvou grafů souvisejících a stromů // The Electronic Journal of Combinatorics. - 1995. - T. 2 . — ISSN 1077-8926 .
  6. ↑ Cameron, van Lint, 1991 , s. 62.
  7. ↑ Cameron, van Lint, 1991 , s. 61.
  8. ↑ Colbourn, Dinitz, 2007 , str. 878, #13,24.
  9. ↑ van Lint, Seidel, 1966
  10. ↑ Cameron, van Lint, 1991 , s. 62, věta 4.11.
  11. ↑ Cameron, van Lint, 1991 , s. 62, věta 4.12.

Literatura