To-tæller

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] .

Eksempler

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   346

Denne 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]

Skift og grafer

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 matrix

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]

Ensartede linjer

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.

Stærkt regelmæssige grafer

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]

Noter

  1. ↑ 1 2 3 Cameron, van Lint, 1991 , s. 58-59.
  2. ↑ G. Eric Moorhouse. To-grafer og skæve to-grafer i endelige geometrier // Lineær algebra og dens anvendelser. - 1995.
  3. ↑ Colbourn, Dinitz, 2007 , s. 876, note 13.2.
  4. ↑ P. J. Cameron. To-grafer og træer // Diskret matematik. - 1994. - T. 127 . - S. 63-74 . - doi : 10.1016/0012-365x(92)00468-7 . , som citeret i Colbourn og Dinitz, 2007 , s. 876, konklusion 13.12.
  5. ↑ Peter J. Cameron. Tælle to-grafer relateret og træer // 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 , s. 878, #13.24.
  9. ↑ van Lint, Seidel, 1966
  10. ↑ Cameron, van Lint, 1991 , s. 62, sætning 4.11.
  11. ↑ Cameron, van Lint, 1991 , s. 62, sætning 4.12.

Litteratur