Kétszámos

A matematikában a kétgráf hármasok (rendezetlen) halmaza, amelyet az X csúcsok véges halmazából választanak ki oly módon, hogy X -ben bármely (rendezetlen) négy páros számú kiválasztott kétgráf hármast tartalmaz. Egy szabályos (homogén) kétgráfban bármely csúcspár a kétgráf ugyanannyi tripletében található. A kétgráfokat az egyenlőszögű vonalakkal , a szabályos kétgráfok és az erősen szabályos gráfokkal , valamint a szabályos kétgráfok véges csoportokkal való kapcsolatát vizsgálják , mivel ezeknek a gráfoknak sok érdekes automorfizmuscsoportja van .

A kétgráfok nem gráfok , és nem tévesztendők össze más objektumokkal, amelyeket a gráfelmélet 2-gráfoknak nevez , különösen a 2-reguláris gráfokkal . Ezek megkülönböztetésére a „kettő” szót használjuk, nem a „2” számot [1] .

A kétgráfokat G. Higman olyan természetes objektumként vezette be, amely néhány egyszerű csoporttal való munka során keletkezik. Azóta Seidel, Taylor és mások intenzíven tanulmányozták őket egyenszögű vonalak, erősen szabályos gráfok és más objektumok halmazainak tanulmányozása terén [2] [1] .

Példák

Az {1, ..., 6} csúcshalmazon a hármasok következő rendezetlen halmaza egy kétgráf:

123 124 135 146 156 236 245 256 345   346

Ez a két gráf szabályos, mert bármely különböző csúcspár pontosan két hármasban végződik.

Adott egy közönséges G = ( V ,  E ) gráf, akkor V - beli csúcsok hármasainak halmaza, amelynek generált részgráfja páratlan számú éllel rendelkezik, kettős gráfot alkot V -n . Bármely kétgráf ábrázolható ebben a formában [3] . Ez a példa azt a szabványos módot mutatja be, hogyan lehet két gráfot normál gráfból felépíteni.

Vegyünk egy bonyolultabb példát. Legyen T egy E élhalmazú fa . Az összes olyan élhármas halmaza, amelyek nem ugyanazon az úton fekszenek T -ben, kétgráfot alkotnak az E halmazon . [4] [5]

Kapcsolás és grafikonok

A kétgráf egyenértékű a gráfok kapcsolási osztályával, valamint az előjeles teljes gráfok (előjeles) kapcsolási osztályával .

A csúcsok halmazának váltása egy (reguláris) gráfban minden egyes csúcspár szomszédságának megváltoztatását jelenti, amelyek közül az egyik a halmazban van, a másik pedig nincs a halmazban - a szomszédos pár nem szomszédos lesz, a nem szomszédos pedig pár szomszédossá válik. Azok az élek, amelyek végpontjai a halmazban vannak, vagy mindkét végpont a halmazon kívül van, nem változnak. A grafikonok váltási egyenértékűek , ha váltással az egyik a másikból megszerezhető. A kapcsolási ekvivalencia osztályt kapcsolási osztálynak nevezzük . A váltást van Lint és Seidel vezette be ( van Lint, Seidel 1966 ), és Seidel fejlesztette ki. A gráfváltás vagy a Seidel váltás elnevezést részben azért vezették be, hogy megkülönböztessék az előjeles gráfváltástól .

A fentebb bemutatott két gráf egy közönséges gráfból történő szabványos felépítésében két gráf akkor és csak akkor adja ugyanazt a kétgráfot, ha kapcsolási ekvivalens, azaz ugyanabba a kapcsolási osztályba tartozik.

Legyen Γ kétgráf egy X halmazon . X bármely x elemére definiálunk egy X csúcshalmaz gráfot , amelyben y és z csúcsok akkor és csak akkor szomszédosak, ha { x , y , z } Γ-hez tartozik. Ebben a gráfban x egy izolált csúcs lesz. Ez a konstrukció megfordítható. Adott egy közönséges G gráf, adjunk hozzá egy új x elemet a G csúcshalmazhoz, és határozzunk meg egy kétgráfot úgy, hogy minden { x , y , z } triplának van y és z szomszédos csúcsa G -ben . Ezt a két gráfot a folyamatábra nyelvben a G gráf x csúcs általi kiterjesztésének nevezzük . [1] Egy szabályos kétgráf adott kapcsolási osztályában legyen Γ x az egyetlen gráf, amelynek az x csúcsa izolált csúcs (egy mindig létezik, csak ki kell venni az osztály bármely gráfját, és át kell váltani viszonylag nem szomszédos x csúcs), és nem tartalmazza magát az x csúcsot . Vagyis a kétgráf Γ x kiterjesztése egy x csúcsgal . A szabályos kétgráfos példában Γ x egy 5 csúcsú ciklus bármely x választására . [6]

A G gráf egy előjeles teljes Σ gráfnak felel meg ugyanazon a csúcshalmazon, amelynek élei negatívak, ha G -hez tartoznak , és pozitívak, ha nem G -hez tartoznak . Ezzel szemben G Σ részgráfja, és minden csúcsból és negatív élből áll. A G kétgráfot úgy is definiálhatjuk, mint a Σ-ban negatív háromszöget (páratlan számú negatív élű háromszöget) alkotó csúcsok hármasainak halmazát. Két előjeles teljes gráf akkor és csak akkor adja meg ugyanazt a kétgráfot, ha váltakozó ekvivalens.

A G és Σ kapcsolása össze van kötve – ugyanazon csúcsok kapcsolása a H gráfot és a megfelelő előjeles teljes gráfot kapja.

Szomszédsági mátrix

A kétgráf szomszédsági mátrixa a megfelelő előjeles teljes gráf szomszédsági mátrixa Vagyis szimmetrikus , az átlóján nullák vannak, az átlón kívüli értékek pedig ±1. Ha G egy Σ előjeles teljes gráfnak megfelelő gráf, ezt a mátrixot G (0, −1, 1) szomszédsági mátrixának vagy Seidel szomszédsági mátrixának [ nevezzük . A Seidel-mátrix főátlóján nullák vannak, a szomszédos csúcsoknak megfelelő elemeknél −1, a nem szomszédos csúcsoknak megfelelő elemeknél +1.

Ha a G és H gráf ugyanabba a kapcsolási osztályba tartozik, akkor a két Seidel szomszédsági mátrix sajátértékeinek multihalmazai G és H esetén egybeesnek, mivel a mátrixok hasonlóak. [7]

Egy V halmaz kétgráfja akkor és csak akkor szabályos, ha a szomszédsági mátrixának csak két különálló sajátértéke van , mondjuk ρ 1 > 0 > ρ 2 , ahol ρ 1 ρ 2 = 1 − | V |. [nyolc]

Equangular lines

Bármely két gráf ekvivalens egy többdimenziós euklideszi térben lévő vonalak halmazával , és az ebből a halmazból származó bármely vonalpár közötti szög azonos. Egy n csúcsú kétgráfból egyenesek halmazát állíthatjuk össze az alábbiak szerint. Legyen −ρ a Seidel-féle szomszédsági mátrix A legkisebb sajátértéke egy kétgráfban , és tételezzük fel, hogy multiplicitása n  −  d . Ekkor a ρ I  +  A mátrix egy d rangú pozitív szemidefinit mátrix , és egy d dimenziójú euklideszi térben n vektor belső szorzatának Gram-mátrixaként ábrázolható . Ezeknek a vektoroknak is ugyanaz a normája (nevezetesen, ) és a páronkénti skaláris szorzat ±1, és az ezen vektorok által átívelt bármely n egyenes pár közötti szög egyenlő φ-vel, ahol cos φ = 1/ρ. Ezzel szemben az euklideszi térben lévő nem merőleges egyenesek bármely halmaza, amelyek bármelyik párja közötti szög azonos, két gráfot ad [9] .

A fenti jelölésben a maximális n számosság kielégíti az n ≤ d (ρ 2 − 1)/(ρ 2 − d ) egyenlőtlenséget, és akkor és csak akkor érjük el a határt, ha a kétgráf szabályos.

Erősen szabályos grafikonok

Az X két gráfjai, amelyek az X összes lehetséges hármasából állnak, és az üresek (amelyek nincsenek hármasaikban), szabályos kétgráfok, de általában triviális kétgráfoknak tekinthetők , és általában kizárják őket a figyelembevételből.

Egy nemtriviális kétgráf egy X halmazon akkor és csak akkor szabályos, ha X-ből bármely x - re a Γ x gráf erősen szabályos , ahol k = 2μ (bármely csúcs foka kétszerese a nem szomszédos párok melletti csúcsok számának kétszerese csúcsok). Ha ez a feltétel igaz X egy x - ére , akkor igaz X minden elemére . [tíz]

Ez azt jelenti, hogy egy nemtriviális szabályos kétgráfnak páros számú csúcsa van.

Ha G egy reguláris gráf, amelynek Γ kiterjesztett kétgráfja n csúcsú, akkor Γ akkor és csak akkor szabályos kétgráf, ha G egy erősen szabályos gráf k , r és s sajátértékekkel úgy, hogy n = 2( k  −  r ) vagy n = 2( k  −  s ). [tizenegy]

Jegyzetek

  1. ↑ 1 2 3 Cameron, van Lint, 1991 , p. 58-59.
  2. ↑ G. Eric Moorhouse. Kétgráfok és ferde kétgráfok véges geometriákban // Lineáris algebra és alkalmazásai. – 1995.
  3. ↑ Colbourn, Dinitz, 2007 , p. 876, 13.2. jegyzet.
  4. ↑ P. J. Cameron. Kétgráfok és fák // Diszkrét matematika. - 1994. - T. 127 . - S. 63-74 . - doi : 10.1016/0012-365x(92)00468-7 . Colbourn és Dinitz, 2007 , p. 876, következtetés 13.12.
  5. ↑ Peter J. Cameron. Counting two-graphs related and trees // The Electronic Journal of Combinatorics. - 1995. - T. 2 . — ISSN 1077-8926 .
  6. ↑ Cameron, van Lint, 1991 , p. 62.
  7. ↑ Cameron, van Lint, 1991 , p. 61.
  8. ↑ Colbourn, Dinitz, 2007 , p. 878, #13.24.
  9. ↑ van Lint, Seidel, 1966
  10. ↑ Cameron, van Lint, 1991 , p. 62, 4.11. Tétel.
  11. ↑ Cameron, van Lint, 1991 , p. 62, 4.12. Tétel.

Irodalom