Două numărătoare

În matematică , un graf cu doi este un set (neordonat) de triple alese dintr-o mulțime finită de vârfuri X în așa fel încât orice patru (neordonat) din X conține un număr par de triple alese cu două graf. Într -un graf regulat (omogen), orice pereche de vârfuri se află în același număr de triplete ale grafului cu două. Două grafuri sunt studiate pentru conexiunea lor cu linii echiunghiulare , conexiunea dintre două grafuri regulate cu grafuri puternic regulate și, de asemenea, pentru conectarea grafurilor regulate cu două grafuri cu grupuri finite , deoarece multe dintre aceste grafuri au grupuri de automorfism interesante .

Cele două grafice nu sunt grafice și nu trebuie confundate cu alte obiecte numite grafice cu două grafice în teoria graficelor , în special graficele cu două grafice regulate . Pentru a distinge între ele, se folosește cuvântul „doi”, nu numărul „2” [1] .

Două grafice au fost introduse de G. Higman ca obiecte naturale care apar atunci când se lucrează cu niște grupuri simple. De atunci, ele au fost studiate intens de Seidel, Taylor și alții în studiul mulțimilor de linii echiunghiulare, grafice puternic regulate și alte obiecte [2] [1] .

Exemple

Pe mulțimea de vârfuri {1, ..., 6}, următorul set neordonat de triple este un grafic cu două:

123 124 135 146 156 236 245 256 345   346

Acest două grafice este obișnuită deoarece orice pereche de vârfuri distincte ajung împreună în exact două triple.

Având în vedere un grafic obișnuit G = ( V ,  E ), atunci o mulțime de triple de vârfuri în V al căror subgraf generat are un număr impar de muchii formează un grafic cu două pe V . Orice două grafice poate fi reprezentată în această formă [3] . Acest exemplu arată modul standard de a construi un grafic cu doi dintr-un grafic normal.

Să luăm un exemplu mai complex. Fie T un arbore cu setul de muchii E . Mulțimea tuturor tripleților de muchii care nu se află pe aceeași cale în T formează un grafic cu doi pe mulțimea E . [4] [5]

Comutare și grafice

Cele două grafice sunt echivalente cu clasa de comutare a graficelor, precum și cu clasa de comutare (semnată) a graficelor complete cu semn .

Schimbarea mulțimii de vârfuri într-un grafic (regulat) înseamnă schimbarea adiacenței fiecărei perechi de vârfuri, dintre care unul este în mulțime, iar celălalt nu este în mulțime - perechea adiacentă devine neadiacentă, iar cea neadiacentă perechea devine adiacentă. Muchiile ale căror puncte finale sunt în set sau ambele puncte finale sunt în afara setului, nu se modifică. Graficele sunt echivalente prin comutare dacă unul poate fi obținut de la celălalt prin comutare. Clasa de echivalență de comutare se numește clasă de comutare . Comutarea a fost introdusă de van Lint și Seidel ( van Lint, Seidel 1966 ) și dezvoltată de Seidel. Numele graph switching sau Seidel switching a fost introdus, parțial, pentru a o deosebi de graph switching .

În construcția standard a două grafice dintr-un grafic obișnuit prezentat mai sus, două grafice dau același două grafice dacă și numai dacă sunt echivalente de comutare, adică aparțin aceleiași clase de comutare.

Fie Γ un grafic cu doi pe o mulțime X . Pentru orice element x din X , definim un grafic X -set de vârfuri în care vârfurile y și z sunt adiacente dacă și numai dacă { x , y , z } aparține lui Γ. În acest grafic, x va fi un vârf izolat. Această construcție este reversibilă. Având în vedere un grafic obișnuit G , adăugați un nou element x la mulțimea de vârfuri G și definiți un graf cu două astfel încât toate triplele { x , y , z } să aibă y și z vârfuri adiacente în G . Acest două grafice în limbajul diagramei de flux se numește extensia graficului G de vârful x . [1] Într-o clasă de comutare dată a unui grafic obișnuit cu două, fie Γ x singurul grafic care are vârful x ca vârf izolat (există întotdeauna unul, trebuie doar să luați orice grafic din clasă și să comutați relativ non- vârfurile x adiacente ), și nu includ vârful x însuși . Adică, un grafic cu doi este o extensie a lui Γ x cu un vârf x . În exemplul obișnuit cu două grafice, Γ x este un ciclu de 5 vârfuri pentru orice alegere de x . [6]

Graficul G corespunde unui grafic complet Σ cu semn pe aceeași mulțime de vârfuri, ale cărui muchii sunt negative dacă aparțin lui G și pozitive dacă nu aparțin lui G . În schimb, G este un subgraf al lui Σ și este format din toate vârfurile și muchiile negative. Un G cu două grafice poate fi definit și ca mulțimea de triplete de vârfuri care formează un triunghi negativ (un triunghi cu un număr impar de muchii negative) în Σ. Două grafice complete semnate dau același două grafice dacă și numai dacă sunt echivalente de comutare.

Comutarea G și Σ sunt conectate - comutarea acelorași vârfuri dă graficul H și graficul complet cu semn corespunzător.

Matricea adiacentei

Matricea de adiacență a unui graf cu două este matricea de adiacență graficului complet cu semn corespunzător. Adică, este simetric , are zerouri pe diagonală, iar valorile în afara diagonalei sunt ±1. Dacă G este un grafic corespunzător unui grafic complet cu semn Σ, această matrice se numește matricea de adiacență (0, −1, 1) sau matricea de adiacență Seidel [ a lui G . Matricea Seidel are zerouri pe diagonala principală, −1 pentru elementele corespunzătoare vârfurilor adiacente și +1 pentru elementele corespunzătoare vârfurilor neadiacente.

Dacă graficele G și H sunt în aceeași clasă de comutare, multiseturile de valori proprii ale celor două matrici de adiacență Seidel pentru G și H coincid, deoarece matricele sunt similare. [7]

Un grafic cu doi pe o mulțime V este regulat dacă și numai dacă matricea sa de adiacență are doar două valori proprii distincte , să spunem ρ 1 > 0 > ρ 2 , unde ρ 1 ρ 2 = 1 − | V |. [opt]

Linii ecuangulare

Orice două grafice este echivalentă cu un set de linii dintr-un spațiu euclidian multidimensional , iar unghiul dintre orice pereche de linii din această mulțime este același. Un set de linii poate fi construit dintr-un graf cu n vârfuri, după cum urmează. Fie −ρ cea mai mică valoare proprie a matricei de adiacență Seidel A a unui graf cu două și presupunem că multiplicitatea sa este n  −  d . Atunci matricea ρ I  +  A este o matrice semidefinită pozitivă de rang d , și poate fi reprezentată ca matrice Gram a produselor interne a n vectori într-un spațiu euclidian de dimensiune d . Acești vectori au, de asemenea, aceeași normă (și anume, ) și produsul scalar pe perechi ±1, iar unghiul dintre orice pereche de n linii acoperite de acești vectori este egal cu φ, unde cos φ = 1/ρ. În schimb, orice set de linii neortogonale din spațiul euclidian, unghiul dintre orice pereche este același, dă un grafic cu două [9] .

În notația de mai sus, cardinalitatea maximă n satisface inegalitatea n ≤ d (ρ 2 − 1)/(ρ 2 − d ), iar limita este atinsă dacă și numai dacă graficul cu doi este regulat.

Grafice puternic regulate

Două grafice pe X constând din toate triplele posibile din X și cele goale (fără triple) sunt două grafice obișnuite, dar sunt de obicei considerate două grafice banale și sunt de obicei excluse din considerare.

Un bigraf netrivial pe o mulțime X este regulat dacă și numai dacă pentru orice x din X , graficul Γ x este puternic regulat cu k = 2μ (gradul oricărui vârf este de două ori numărul de vârfuri adiacente ambelor perechi neadiacente). de vârfuri). Dacă această condiție este adevărată pentru un x din X , atunci este adevărată pentru toate elementele lui X . [zece]

Acest lucru implică faptul că un graf regulat netrivial are un număr par de vârfuri.

Dacă G este un grafic obișnuit al cărui graf extins cu două Γ are n vârfuri, atunci Γ este un grafic cu două obișnuit dacă și numai dacă G este un grafic puternic regulat cu valori proprii k , r și s astfel încât n = 2( k  −  r ) sau n = 2( k  −  s ). [unsprezece]

Note

  1. ↑ 1 2 3 Cameron, van Lint, 1991 , p. 58-59.
  2. ↑ G. Eric Moorhouse. Two-Graphs și Skew Two-Graphs în geometrii finite // Algebra liniară și aplicațiile sale. — 1995.
  3. ↑ Colbourn, Dinitz, 2007 , p. 876, nota 13.2.
  4. ↑ P. J. Cameron. Două grafice și arbori // Matematică discretă. - 1994. - T. 127 . - S. 63-74 . - doi : 10.1016/0012-365x(92)00468-7 . , după cum este citat în Colbourn și Dinitz, 2007 , p. 876, încheierea 13.12.
  5. ↑ Peter J. Cameron. Numărarea două grafice legate și arbori // 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, Teorema 4.11.
  11. ↑ Cameron, van Lint, 1991 , p. 62, Teorema 4.12.

Literatură