Dwa wykresy

W matematyce dwugraf jest zbiorem (nieuporządkowanych) trójek wybranych ze skończonego zbioru wierzchołków X , tak że każda (nieuporządkowana) czwórka z X zawiera parzystą liczbę trójek dwugrafu. Regularny w tej samej liczbie trójek dwugrafu. Dwugrafy były badane ze względu na ich związek z liniami równokątnymi , a dla regularnych dwóch wykresów, silnie regularnymi grafami , a także skończonymi grupami ponieważ wiele regularnych dwugrafów ma interesujące grupy automorfizmów .

Dwuwykres nie jest grafem i nie należy go mylić z innymi obiektami zwanymi w teorii grafów 2-wykresami , takimi jak 2-wykresy regularne .

Przykłady

Na zbiorze wierzchołków {1,...,6} następujący zbiór nieuporządkowanych trójek jest dwugrafem:

123 124 135 146 156 236 245 256 345 346

Ten dwugraf jest regularnym dwugrafem, ponieważ każda para odrębnych wierzchołków występuje razem w dokładnie dwóch trójkach.

Mając prosty graf G = ( V , E ), zbiór trójek zbioru wierzchołków V , którego indukowany podgraf ma nieparzystą liczbę krawędzi, tworzy dwugraf na zbiorze V . Każdy dwugraf można przedstawić w ten sposób. Ten przykład jest określany jako standardowa konstrukcja dwuwykresu z prostego wykresu.

Jako bardziej złożony przykład, niech T będzie drzewem o zbiorze krawędzi E . Zbiór wszystkich trójek E , które nie są zawarte w ścieżce T , tworzy dwugraf na zbiorze E .

Przełączanie i wykresy

Przełączanie {X,Y} na wykresie

Dwugraf jest równoważny klasie przełączania grafów, a także (podpisanej) klasie przełączania pełnych grafów ze znakiem .

Przełączanie zestawu wierzchołków w (prostym) grafie oznacza odwrócenie sąsiedztwa każdej pary wierzchołków, jednego w zestawie, a drugiego poza zestawem: w ten sposób zestaw krawędzi jest zmieniany, tak że sąsiednia para staje się nieprzylegającą i nieprzylegającą parą staje się sąsiadem. Krawędzie, których oba punkty końcowe znajdują się w zbiorze lub nie znajdują się w zbiorze, nie są zmieniane. Wykresy są równoważne przełączaniu , jeśli jeden można uzyskać z drugiego przez przełączanie. Klasa równoważności grafów przełączanych nazywana jest klasą przełączania . Przełączanie zostało wprowadzone przez van Linta i Seidela (1966) i opracowany przez firmę Seidel; nazwano to przełączaniem grafów lub przełączaniem Seidela , częściowo w celu odróżnienia od przełączania podpisanych grafów .

W standardowej konstrukcji dwuwykresu z prostego wykresu podanego powyżej, dwa wykresy dadzą ten sam dwuwykres wtedy i tylko wtedy, gdy są równoważne przy przełączaniu, to znaczy należą do tej samej klasy przełączania.

Niech Γ będzie dwugrafem na zbiorze X . Dla dowolnego elementu x z X , zdefiniuj graf Γ x ze zbiorem wierzchołków X mającym sąsiadujące wierzchołki y i z wtedy i tylko wtedy, gdy { x , y , z } jest w Γ. Na tym grafie x będzie izolowanym wierzchołkiem. Ta konstrukcja jest odwracalna; biorąc pod uwagę prosty graf G , dołącz nowy element x do zbioru wierzchołków G , zachowując ten sam zestaw krawędzi i zastosuj powyższą standardową konstrukcję.

Grafowi G odpowiada pełny graf Σ ze znakiem w tym samym zbiorze wierzchołków, którego krawędzie są ujemne, jeśli w G , i dodatnie, jeśli nie w G. I odwrotnie, G jest podwykresem Σ, który składa się ze wszystkich wierzchołków i wszystkich ujemnych krawędzi. Dwugraf G można również zdefiniować jako zbiór trójek wierzchołków, które wspierają trójkąt ujemny (trójkąt z nieparzystą liczbą ujemnych krawędzi) w Σ. Dwa podpisane kompletne grafy dają ten sam dwugraf wtedy i tylko wtedy, gdy są równoważne przy przełączaniu.

Przełączanie G i Σ są ze sobą powiązane: przełączanie tych samych wierzchołków w obu daje graf H i odpowiadający mu pełny graf ze znakiem.

Macierz sąsiedztwa

Macierz sąsiedztwa wykresu dwuwierszowego jest macierzą sąsiedztwa odpowiedniego pełnego grafu ze znakiem; więc jest symetryczny , ma zero na przekątnej i ma wpisy ± 1 poza przekątną. Jeśli G jest wykresem odpowiadającym pełnemu grafowi ze znakiem Σ, macierz ta nazywana jest macierzą sąsiedztwa (0, −1, 1) lub macierzą sąsiedztwa Seidela G . Macierz Seidela ma zero wpisów na głównej przekątnej, wpisy -1 dla wierzchołków sąsiednich i wpisy +1 dla wierzchołków nieprzylegających.

Jeśli wykresy G i H należą do tej samej klasy przełączania, multizbiór wartości własnych dwóch macierzy sąsiedztwa Seidela G i H pokrywa się, ponieważ macierze są podobne.

Dwugraf na zbiorze V jest regularny wtedy i tylko wtedy, gdy jego macierz sąsiedztwa ma tylko dwie różne wartości własne ρ 1 > 0 > ρ 2 powiedzmy, gdzie ρ 1 ρ 2 = 1 - | V |.

Linie równoramienne

Każdy dwuwykres jest równoważny zbiorowi linii w jakiejś wymiarowej przestrzeni euklidesowej, z których każda para spotyka się pod tym samym kątem. Zestaw linii zbudowanych z dwóch wykresów na n wierzchołkach otrzymuje się w następujący sposób. Niech -ρ będzie najmniejszą wartością własną macierzy sąsiedztwa Seidela , A , dwugrafu i załóżmy, że ma krotność n - d . Wtedy macierz ρ I + A jest dodatnio półokreślona rzędu d , a zatem może być przedstawiona jako Macierz Grama iloczynów wewnętrznych n wektorów w euklidesowej przestrzeni d . Ponieważ te wektory mają tę samą normę (mianowicie wzajemne iloczyny wewnętrzne ± 1, dowolna para n linii, które nimi rozpinają, spotyka się pod tym samym kątem φ gdzie cos φ = 1/ρ. I odwrotnie, każdy zestaw nieortogonalnych równokątnych linii w przestrzeni euklidesowej może dać początek dwuwykresowi (zobacz konstrukcje równokątne ).

Przy powyższym zapisie maksymalna liczność n spełnia n d 2 - 1)/(ρ 2 - d ) i granica jest osiągnięta wtedy i tylko wtedy, gdy dwuwykres jest regularny.

Notatki

  • Brouwer, AE , Cohen, AM i Neumaier, A. (1989), Distance-Regular Graphs. Springer-Verlag w Berlinie. Sekcje 1.5, 3.8, 7.6C.
  •   Cameron, PJ; van Lint, JH (1991), Designs, Graphs, Codes and their Links , London Mathematical Society Student Texts 22, Cambridge University Press, ISBN 978-0-521-42385-4
  •   Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (wyd. 2), Boca Raton: Chapman & Hall/ CRC, s. 875–882, ISBN 1-58488-506-8
  • Chris Godsil and Gordon Royle (2001), Teoria grafów algebraicznych. Absolwent Teksty z matematyki, tom. 207. Springer-Verlag, Nowy Jork. Rozdział 11.
  • Seidel, JJ (1976), Przegląd dwóch wykresów. W: Colloquio Internazionale sulle Teorie Combinatorie (Proceedings, Rzym, 1973), tom. I, s. 481–511. Atti dei Convegni Lincei, nr 17. Accademia Nazionale dei Lincei, Rzym.
  • Taylor, DE (1977), Regularne 2-wykresy. Proceedings of the London Mathematical Society (3), tom. 35, s. 257–274.
  • van Lint, JH; Seidel, JJ (1966), „Zestawy punktów równobocznych w geometrii eliptycznej”, Indagationes Mathematicae , Proc. Koninkl. Ned. Akad. Wetenschap. Ser. A 69, 28 : 335–348