I matematik er en to-graf et (uordnet) sæt af tripler valgt fra et endeligt sæt af toppunkter X på en sådan måde, at enhver (uordnet) fire i X indeholder et lige antal valgte to-graf-tripler. I en regulær (homogen) to-graf ligger ethvert par af hjørner i det samme antal tripletter af to-grafen. To-grafer studeres for deres forbindelse med ensvinklede linjer , forbindelsen af regulære to-grafer med stærkt regelmæssige grafer , og også for forbindelsen af regulære to-grafer med endelige grupper , da mange af disse grafer har interessante automorfigrupper .
To-grafer er ikke grafer og bør ikke forveksles med andre objekter, der kaldes 2-grafer i grafteori , især 2-regulære grafer . For at skelne mellem dem bruges ordet "to", ikke tallet "2" [1] .
To-grafer blev introduceret af G. Higman som naturlige objekter, der opstår, når man arbejder med nogle simple grupper. Siden da er de blevet intensivt undersøgt af Seidel, Taylor og andre i studiet af sæt af ensvinklede linjer, stærkt regulære grafer og andre objekter [2] [1] .
På toppunktet {1, ..., 6} er det følgende uordnede sæt af tripler en to-graf:
123 124 135 146 156 236 245 256 345 346Denne to-graf er regelmæssig, fordi ethvert par adskilte hjørner ender sammen i præcis to tripler.
Givet en almindelig graf G = ( V , E ), danner et sæt tripler af hjørner i V , hvis genererede undergraf har et ulige antal kanter, en to-graf på V . Enhver to-graf kan repræsenteres i denne form [3] . Dette eksempel viser standardmåden til at bygge en to-graf fra en normal graf.
Lad os tage et mere komplekst eksempel. Lad T være et træ med kantsæt E . Mættet af alle trillinger af kanter, der ikke ligger på samme vej i T , danner en to-graf på sættet E . [4] [5]
To-grafen er ækvivalent med omskiftningsklassen af grafer, såvel som (fortegns-) omskiftningsklassen af fortegnede komplette grafer .
At skifte sæt af knudepunkter i en (regelmæssig) graf betyder at ændre tilgrænsende af hvert par knudepunkter, hvoraf den ene er i sættet, og den anden ikke er i sættet - det tilstødende par bliver ikke-tilstødende, og det ikke-tilstødende par par bliver tilstødende. Kanter, hvis endepunkter er i sættet, eller begge endepunkter er uden for sættet, ændres ikke. Grafer er skifteækvivalente , hvis den ene kan opnås fra den anden ved at skifte. Skifteækvivalensklassen kaldes skifteklassen . Switching blev introduceret af van Lint og Seidel ( van Lint, Seidel 1966 ) og udviklet af Seidel. Navnet graph switching eller Seidel switching blev introduceret, delvist for at skelne det fra signed graph switching .
I standardkonstruktionen af to grafer fra en almindelig graf givet ovenfor, giver to grafer den samme to-graf, hvis og kun hvis de er skifteækvivalente, det vil sige, at de tilhører den samme skifteklasse.
Lad Γ være en to-graf på en mængde X . For ethvert element x fra X definerer vi en vertex-sæt graf X , hvor spidserne y og z er tilstødende, hvis og kun hvis { x , y , z } hører til Γ. I denne graf vil x være et isoleret toppunkt. Denne konstruktion er reversibel. Givet en almindelig graf G , tilføje et nyt element x til toppunktet G og definere en to-graf, således at alle tripler { x , y , z } har y og z tilstødende hjørner i G . Denne to-graf i flowchart-sprog kaldes forlængelsen af grafen G med toppunktet x . [1] I en given omskiftningsklasse af en regulær to-graf, lad Γ x være den eneste graf, der har toppunkt x som et isoleret toppunkt (et eksisterer altid, du skal bare tage en hvilken som helst graf i klassen og skifte relativt ikke- tilstødende x toppunkter), og inkluderer ikke selve toppunktet x . Det vil sige, at en to-graf er en forlængelse af Γ x med et toppunkt x . I det almindelige eksempel med to grafer er Γ x en cyklus med 5 hjørner for ethvert valg af x . [6]
Grafen G svarer til en komplet graf Σ med fortegn på det samme sæt af hjørner, hvis kanter er negative, hvis de hører til G , og positive, hvis de ikke hører til G . Omvendt er G en undergraf af Σ og består af alle hjørner og negative kanter. En to-graf G kan også defineres som det sæt af tripletter af hjørner, der danner en negativ trekant (en trekant med et ulige antal negative kanter) i Σ. To fortegnede komplette grafer giver den samme to-graf, hvis og kun hvis de skifter ækvivalente.
Omskifter G og Σ er forbundet — skift af de samme hjørner giver grafen H og den tilsvarende fortegnede komplette graf.
Adjacency-matrixen af en to-graf er adjacency-matricen den tilsvarende fortegnede komplette graf. Det vil sige, det er symmetrisk , har nuller på diagonalen, og off-diagonale værdier er ±1. Hvis G er en graf, der svarer til en komplet graf med fortegn Σ, kaldes denne matrix (0, −1, 1) adjacency-matrixen eller Seidel-adjacency-matrixen [ af G . Seidel-matricen har nuller på hoveddiagonalen, −1 for elementer, der svarer til tilstødende hjørner, og +1 for elementer, der svarer til ikke-tilstødende knudepunkter.
Hvis graferne G og H er i den samme koblingsklasse, falder multisæt af egenværdier af de to Seidel tilstødende matricer for G og H sammen, fordi matricerne er ens. [7]
En to-graf på en mængde V er regulær, hvis og kun hvis dens tilstødende matrix kun har to distinkte egenværdier , f.eks. ρ 1 > 0 > ρ 2 , hvor ρ 1 ρ 2 = 1 − | V |. [otte]
Enhver to-graf svarer til et sæt linjer i et eller andet multidimensionelt euklidisk rum , og vinklen mellem ethvert linjepar fra dette sæt er den samme. Et sæt linjer kan konstrueres ud fra en to-graf med n hjørner som følger. Lad −ρ være den mindste egenværdi af Seidel-adjacency-matrixen A af en to-graf, og antag, at dens multiplicitet er n − d . Så er matrixen ρ I + A en positiv semibestemt matrix af rang d , og den kan repræsenteres som Gram-matricen af indre produkter af n vektorer i et euklidisk rum med dimension d . Disse vektorer har også den samme norm (nemlig, ) og det parvise skalarprodukt ±1, og vinklen mellem ethvert par af n linjer, som disse vektorer spænder over, er lig med φ, hvor cos φ = 1/ρ. Omvendt giver ethvert sæt af ikke-ortogonale linjer i det euklidiske rum, hvis vinkel mellem ethvert par er den samme, en to-graf [9] .
I notationen ovenfor opfylder den maksimale kardinalitet n uligheden n ≤ d (ρ 2 − 1)/(ρ 2 − d ), og grænsen nås, hvis og kun hvis to-grafen er regulær.
To-grafer på X bestående af alle mulige tripler fra X og tomme (der ikke har nogen tripler) er almindelige to-grafer, men de betragtes normalt som trivielle to-grafer og er normalt udelukket fra overvejelse.
En ikke-triviel to-graf på et sæt X er regulær, hvis og kun hvis grafen Γ x for et hvilket som helst x fra X er meget regulært med k = 2μ (graden af ethvert toppunkt er det dobbelte af antallet af hjørner, der støder op til begge i ethvert ikke-tilstødende par af hjørner). Hvis denne betingelse er sand for en x af X , så er den sand for alle elementer af X. [ti]
Dette indebærer, at en ikke-triviel regulær to-graf har et lige antal hjørner.
Hvis G er en regulær graf, hvis udvidede to-graf Γ har n toppunkter, så er Γ en regulær to-graf, hvis og kun hvis G er en meget regulær graf med egenværdier k , r , og s således, at n = 2( k − r ) eller n = 2( k − s ). [elleve]