Kaksilukuinen

Matematiikassa kaksigrafiikka on (järjestämätön) joukko kolmioita, jotka valitaan äärellisestä kärkijoukosta X siten , että mikä tahansa (järjestämätön) neljä X :ssä sisältää parillisen määrän valittuja kahden graafin kolmioita. Säännöllisessä (homogeenisessa) kaksigrafiikassa mikä tahansa kärkipari on samassa määrässä kaksigraafin triplettejä. Kaksikuvaajien yhteyttä tutkitaan tasakulmaisten viivojen kanssa, säännöllisten kaksikuvaajien yhteyttä vahvasti säännöllisiin kaavioihin sekä myös säännöllisten kaksikuvaajien yhteyttä äärellisiin ryhmiin , koska monissa näistä kaavioista on mielenkiintoisia automorfismiryhmiä .

Kaksikuvaajat eivät ole kaavioita , eikä niitä pidä sekoittaa muihin objekteihin, joita graafiteoriassa kutsutaan 2-kaavioiksi , etenkään 2-säännöllisiin kaavioihin . Niiden erottamiseksi käytetään sanaa "kaksi", ei numeroa "2" [1] .

G. Higman esitteli kaksikaavioita luonnollisina esineinä, jotka syntyvät joidenkin yksinkertaisten ryhmien kanssa työskennellessä. Siitä lähtien Seidel, Taylor ja muut ovat tutkineet niitä intensiivisesti tasakulmaisten viivojen, vahvasti säännöllisten kuvaajien ja muiden objektien joukoissa [2] [1] .

Esimerkkejä

Huippujoukossa {1, ..., 6} seuraava järjestämätön kolmoisjoukko on kaksigraafinen:

123 124 135 146 156 236 245 256 345   346

Tämä kaksikuvaaja on säännöllinen, koska mikä tahansa erillisten kärkien pari päätyy yhteen tasan kahteen kolmioon.

Kun on annettu tavallinen graafi G = ( V ,  E ), silloin joukko V :n kärkikolmioita, joiden generoidussa osagraafissa on pariton määrä reunoja, muodostaa kaksigraafin V :llä . Mikä tahansa kaksigrafiikka voidaan esittää tässä muodossa [3] . Tämä esimerkki näyttää tavallisen tavan rakentaa kaksikuvaaja normaalista kaaviosta.

Otetaan monimutkaisempi esimerkki. Olkoon T puu, jonka reunajoukko on E . Kaikkien reunojen triplettien joukko, jotka eivät ole samalla polulla T :ssä, muodostavat kaksigraafin joukossa E . [4] [5]

Vaihtaminen ja kaaviot

Kaksigrafiikka vastaa graafien kytkentäluokkaa sekä etumerkittyjen kokonaisten graafien (merkitty) kytkentäluokkaa .

Piikkijoukon vaihtaminen (säännöllisessä) graafissa tarkoittaa kunkin pisteparin vierekkäisyyden muuttamista, joista toinen on joukossa ja toinen ei ole joukossa - viereinen pari ei ole vierekkäinen ja ei-viereinen parista tulee vierekkäinen. Reunat, joiden päätepisteet ovat joukossa tai molemmat päätepisteet ovat joukon ulkopuolella, eivät muutu. Graafit ovat vaihtovastaavia , jos toinen voidaan saada toisesta vaihtamalla. Kytkentäekvivalenssiluokkaa kutsutaan kytkentäluokiksi . Switchingin esittelivät van Lint ja Seidel ( van Lint, Seidel 1966 ), ja sen kehitti Seidel. Nimi graph switching tai Seidel switching otettiin käyttöön osittain sen erottamiseksi etumerkitystä graafin vaihdosta .

Yllä annetussa kahden graafin vakiokonstruktiossa tavallisesta graafista kaksi kuvaajaa antavat saman kaksigraafin, jos ja vain jos ne ovat kytkentäekvivalenttia, eli ne kuuluvat samaan kytkentäluokkaan.

Olkoon Γ kaksikuvaaja joukolla X . Jokaiselle X:n alkiolle x määritetään kärkijoukkograafi X , jossa kärjet y ja z ovat vierekkäisiä, jos ja vain jos { x , y , z } kuuluu Γ:ään. Tässä kaaviossa x on eristetty kärki. Tämä rakenne on käännettävä. Kun on annettu tavallinen graafi G , lisää uusi elementti x pistejoukkoon G ja määritä kaksigraafi siten, että kaikilla kolmioilla { x , y , z } on y ja z vierekkäiset G :n kärjet . Tätä kahta kuvaajaa vuokaaviokielessä kutsutaan graafin G jatkeeksi kärjen x mukaan . [1] Olkoon Γ x säännöllisen kahden graafin tietyssä kytkentäluokassa ainoa graafi, jonka kärkipiste x on eristettynä (yksi on aina olemassa, sinun tarvitsee vain ottaa mikä tahansa luokan graafi ja vaihtaa suhteellisen ei- vierekkäiset x -pisteet), eivätkä sisällä itse kärkeä x . Toisin sanoen kaksigrafiikka on Γ x :n laajennus kärjellä x . Tavallisessa kahden graafin esimerkissä Γ x on 5-pisteen sykli mille tahansa x :n valinnalle . [6]

Graafi G vastaa etumerkittyä täydellistä graafia Σ samalla kärkijoukolla, jonka reunat ovat negatiiviset, jos ne kuuluvat G :hen , ja positiiviset, jos ne eivät kuulu G :hen . Sitä vastoin G on Σ:n osagraafi ja koostuu kaikista pisteistä ja negatiivisista reunoista. Kaksigrafiikka G voidaan myös määritellä joukoksi pisteiden kolmioita, jotka muodostavat negatiivisen kolmion (kolmion, jossa on pariton määrä negatiivisia reunoja) Σ:ssa. Kaksi etumerkillä varustettua täydellistä kuvaajaa antavat saman kaksikuvaajan silloin ja vain, jos ne ovat vaihtavia ekvivalentteja.

Vaihto G ja Σ ovat yhteydessä — samojen kärkien vaihtaminen antaa graafin H ja vastaavan etumerkillisen täydellisen graafin.

Vierekkäisyysmatriisi

Kahden graafin viereisyysmatriisi on vastaavan etumerkityn täydellisen graafin viereisyysmatriisi Eli se on symmetrinen , sen diagonaalissa on nollia ja diagonaalin ulkopuoliset arvot ovat ±1. Jos G on graafi, joka vastaa etumerkittyä täydellistä graafia Σ, tätä matriisia kutsutaan (0, −1, 1) viereisyysmatriisiksi tai G : n Seidelin viereisyysmatriisiksi [ . Seidel-matriisin päädiagonaalissa on nollia, -1 vierekkäisiä kärkipisteitä vastaaville elementeille ja +1 elementeille, jotka vastaavat ei-vierekkäisiä kärkipisteitä.

Jos graafit G ja H ovat samassa kytkentäluokassa, kahden Seidelin viereisyysmatriisin G :n ja H : n ominaisarvojen multisarjat osuvat yhteen, koska matriisit ovat samanlaisia. [7]

Kaksigrafiikka joukolla V on säännöllinen silloin ja vain, jos sen viereisyysmatriisissa on vain kaksi erillistä ominaisarvoa , esimerkiksi ρ 1 > 0 > ρ 2 , missä ρ 1 ρ 2 = 1 − | V |. [kahdeksan]

Equangular lines

Mikä tahansa kaksikuvaaja vastaa rivijoukkoa jossakin moniulotteisessa euklidisessa avaruudessa , ja minkä tahansa tämän joukon juovaparin välinen kulma on sama. Joukko viivoja voidaan rakentaa kahdesta graafista, jossa on n kärkeä seuraavasti. Olkoon −ρ kaksigrafisen Seidelin viereisyysmatriisin A pienin ominaisarvo ja oletetaan, että sen monikertaisuus on n  −  d . Tällöin matriisi ρ I  +  A on positiivinen puolimääräinen matriisi, jolla on d , ja se voidaan esittää n vektorin sisätulojen Gram-matriisina euklidisessa avaruudessa, jonka ulottuvuus on d . Näillä vektoreilla on myös sama normi (nimittäin, ) ja pareittainen skalaaritulo ±1, ja minkä tahansa näiden vektorien ylittämän n suoraparin välinen kulma on yhtä suuri kuin φ, missä cos φ = 1/ρ. Sitä vastoin mikä tahansa joukko ei-ortogonaalisia viivoja euklidisessa avaruudessa, jonka minkä tahansa parin välinen kulma on sama, antaa kaksikuvaajan [9] .

Yllä olevassa merkinnässä maksimikardinaliteetti n täyttää epäyhtälön n ≤ d (ρ 2 − 1)/(ρ 2 − d ), ja raja saavutetaan silloin ja vain, jos kaksigraafi on säännöllinen.

Hyvin säännölliset kaaviot

X : n kaksikuvaajat, jotka koostuvat X :n kaikista mahdollisista kolmioista ja tyhjistä (joissa ei ole kolmoisia) ovat tavanomaisia ​​kaksikuvaajia, mutta niitä pidetään yleensä triviaaleina kaksigrafeina ja ne jätetään yleensä huomiotta.

Ei-triviaali kaksikuvaaja joukossa X on säännöllinen silloin ja vain, jos mille tahansa x : lle graafi Γ x on vahvasti säännöllinen , kun k = 2μ (mikä tahansa kärjen aste on kaksinkertainen minkä tahansa ei-viereisen parin molempien viereisten kärkien määrä pisteistä). Jos tämä ehto on tosi yhdelle X :n x : lle , niin se pätee X :n kaikille elementeille . [kymmenen]

Tämä tarkoittaa, että ei-triviaalisella säännöllisellä kaksigraafilla on parillinen määrä pisteitä.

Jos G on säännöllinen graafi, jonka laajennetulla kaksigraafilla Γ on n kärkeä, niin Γ on säännöllinen kaksigraafinen silloin ja vain jos G on vahvasti säännöllinen graafi, jonka ominaisarvot k , r ja s ovat sellaiset, että n = 2( k  −  r ) tai n = 2( k  −  s ). [yksitoista]

Muistiinpanot

  1. ↑ 1 2 3 Cameron, van Lint, 1991 , s. 58-59.
  2. ↑ G. Eric Moorhouse. Kaksikuvaaja ja vino kaksikuvaaja äärellisissä geometrioissa // Lineaarinen algebra ja sen sovellukset. – 1995.
  3. ↑ Colbourn, Dinitz, 2007 , s. 876, huomautus 13.2.
  4. ↑ P. J. Cameron. Kaksikuvaajat ja puut // Diskreetti matematiikka. - 1994. - T. 127 . - S. 63-74 . - doi : 10.1016/0012-365x(92)00468-7 . , kuten viitataan julkaisussa Colbourn ja Dinitz, 2007 , s. 876, päätös 13.12.
  5. ↑ Peter J. Cameron. Kahden kaavion ja puiden laskeminen // 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, Lause 4.11.
  11. ↑ Cameron, van Lint, 1991 , s. 62, Lause 4.12.

Kirjallisuus