Teoria grafów spektralnych - Spectral graph theory

W matematyce , widmowej teorii wykres jest badanie właściwościach wykres w stosunku do charakterystyki wielomianowych , wartości własnych oraz wektorów własnych macierzy związane z wykresu, na przykład z matrycy przylegania lub Laplace'a matrycy .

Macierz sąsiedztwa prostego grafu nieskierowanego jest rzeczywistą macierzą symetryczną, a zatem jest ortogonalnie diagonalizowalna ; jego wartości własne są rzeczywistymi algebraicznymi liczbami całkowitymi .

Chociaż macierz sąsiedztwa zależy od oznakowania wierzchołków, jej widmo jest niezmiennikiem grafu , chociaż nie jest pełne.

Teoria grafów spektralnych dotyczy również parametrów grafów, które są definiowane przez wielokrotności wartości własnych macierzy powiązanych z grafem, takich jak liczba Colina de Verdière'a .

Wykresy kospektralne

Dwa grafy nazywane są kospektralnymi lub izospektralnymi, jeśli macierze sąsiedztwa grafów są izospektralne , to znaczy, jeśli macierze sąsiedztwa mają równe zestawy wartości własnych.

Grafy kospektralne nie muszą być izomorficzne , ale grafy izomorficzne są zawsze kospektralne.

Wykresy określone przez ich widmo

Mówi się, że wykres jest określony przez jego widmo, jeśli jakikolwiek inny wykres o tym samym widmie, co jest izomorficzny z . ${\ Displaystyle G}$${\ Displaystyle G}$${\ Displaystyle G}$

Niektóre pierwsze przykłady rodzin grafów, które są określone przez ich widmo, obejmują:

• W graf pełny .
• Skończone drzewa przypominające gwiazdy .

Współpracownicy kospektralni

Mówi się, że para wykresów to wiązania kospektralne, jeśli mają to samo widmo, ale nie są izomorficzne.

Najmniejsza para wiązań kospektralnych to { K _1,4 , C ₄ ∪ K ₁ }, składająca się z gwiazdy 5-wierzchołkowej i połączenia grafu cyklu 4-wierzchołkowego i grafu jednowierzchołkowego, jak donoszą Collatz i Sinogowitz w 1957.

Najmniejsza para wielościennych kospektralnych partnerów to enneahedra z ośmioma wierzchołkami.

Znajdowanie grafów kospektralnych

Prawie wszystkie drzewa są kospektralne, tj. wraz ze wzrostem liczby wierzchołków ułamek drzew, dla których istnieje drzewo kospektralne, wynosi 1.

Para regularnych wykresów jest kospektralna wtedy i tylko wtedy, gdy ich uzupełnienia są kospektralne.

Para wykresów regularnych odległości jest kospektralna wtedy i tylko wtedy, gdy mają ten sam układ przecięcia.

Wykresy kospektralne można również konstruować za pomocą metody Sunada .

Innym ważnym źródłem grafów kospektralnych są grafy współliniowości punktowej i grafy przecięcia linii dla geometrii punkt-linia . Wykresy te są zawsze kospektralne, ale często nie są izomorficzne.

Nierówność Cheegera

Słynna nierówność Cheegera z geometrii riemannowskiej ma dyskretny analog obejmujący macierz Laplace'a; jest to być może najważniejsze twierdzenie w teorii grafów spektralnych i jeden z najbardziej użytecznych faktów w zastosowaniach algorytmicznych. Przybliża najrzadsze cięcie wykresu przez drugą wartość własną jego laplace'a.

Stała Cheegera

Cheeger stałej (również Cheeger ilość lub ilość isoperimetric ) o wykresie jest liczbowa miara czy wykres ma „wąskiego gardła”. Stała Cheeger jako miara „bottleneckedness” cieszy się dużym zainteresowaniem w wielu dziedzinach, na przykład: Konstruowanie dobrze połączone sieci komputerów , kart tasowanie i topologii niskowymiarowa (w szczególności badanie hiperbolicznych 3- kolektorów ).

Bardziej formalnie, stała Cheeger h ( G ) grafu G na n wierzchołkach jest zdefiniowana jako

${\ Displaystyle h (G) = \ min _ {0 < | S | \ leq {\ Frac {n} {2}}} {\ Frac {| \ częściowy (S) |} {| S |}}}$

w której minimum jest na niepustych wszystkie zestawy S o co najwyżej n / 2 wierzchołki ∂ ( S ) jest ograniczenie krawędzi z S , to znaczy zestaw krawędzi z dokładnie jednym punkcie końcowym w S .

Nierówność Cheegera

Gdy wykres G jest d- regularny, istnieje zależność między h ( G ) a przerwą widmową d − λ ₂ z G . Nierówność spowodowana przez Dodziuka i niezależnie Alona i Milmana stwierdza, że:

${\ Displaystyle {\ Frac {1} {2}} (d \ lambda _ {2}) \ leq h (G) \ leq {\ sqrt {2 d (d \ lambda _ {2})}}.}$

Ta nierówność jest ściśle związana z wiązaniem Cheegera dla łańcuchów Markowa i może być postrzegana jako dyskretna wersja nierówności Cheegera w geometrii riemannowskiej .

Dla ogólnych grafów, które niekoniecznie są regularne, alternatywną nierówność podaje Chung

${\ Displaystyle 2 {\ mathbf {\ lambda} } \ geq {\ mathbf {h} } (g) \ geq {\ frac {\ lambda ^ {2} (g)} {2}}}$

używając znormalizowanej wersji stałej Cheeger ${\ Displaystyle {\ mathbf {h} } (G)}$

${\ Displaystyle {\ mathbf {h} } (G) = \ min _ {\ pusty zbiór \ nie = S \ podzbiór V (G)} {\ Frac {| \ częściowy (S) |} {\ min ({\ operator {vol} }(S),{\mathrm {vol} }({\bar {S}}))}}}$

gdzie jest sumą stopni wierzchołków w i jest najmniejszą nietrywialną wartością własną znormalizowanego Laplace'a, pod warunkiem, że jest połączona. ${\ Displaystyle {\ operatorname {vol} } (Y)}$${\ Displaystyle Y}$${\ Displaystyle \ lambda}$${\ Displaystyle G}$

Nierówność Hoffmana-Delsarte

Jest wartością własną związany na niezależnych zestawów w regularnych wykresów , pierwotnie z powodu Alan J. Hoffmana i Philippe Delsarte.

Załóżmy, że jest to graf regularny na wierzchołkach o najmniejszej wartości własnej . Następnie:${\ Displaystyle G}$${\displaystyle k}$${\ Displaystyle n}$${\ Displaystyle \ lambda _ {\ operatorka {min}}}$

gdzie oznacza jego numer niezależności . ${\ Displaystyle \ alfa (G)}$

Wiązanie to zostało zastosowane do ustalenia m.in. algebraicznych dowodów twierdzenia Erdősa–Ko–Rado i jego odpowiednika dla przecinających się rodzin podprzestrzeni nad ciałami skończonymi .

W przypadku grafów ogólnych, które niekoniecznie są regularne, podobne górne ograniczenie liczby niezależności można wyprowadzić za pomocą maksymalnej wartości własnej znormalizowanego Laplace'a : ${\ Displaystyle \ lambda '_ {max}}$${\ Displaystyle G}$

$${\ Displaystyle \ alfa (G) \ leq n (1-{\ Frac {1} {\ lambda '_ {\ operatorname {max}}}}) {\ Frac {\ operatorname {maxdeg}} {\ operatorname {mindeg } }}}$$

gdzie i oznaczają odpowiednio maksymalny i minimalny stopień w . Jest to konsekwencja bardziej ogólnej nierówności (s. 109 w ): ${\displaystyle {\mathrm {maxdeg}}}$${\displaystyle {\mathrm {mindeg}}}$${\ Displaystyle G}$

$${\ Displaystyle {\ operatorname {vol}} (X) \ leq (1-{\ Frac {1} {\ lambda '_ {\ operatorname {max}}}}) {\ operatorname {vol}} (V (G) ))}$$

gdzie jest niezależnym zbiorem wierzchołków i oznacza sumę stopni wierzchołków w . ${\ Displaystyle X}$${\ Displaystyle {\ operatorname {vol} } (Y)}$${\ Displaystyle Y}$

Rys historyczny

Teoria grafów spektralnych pojawiła się w latach 50. i 60. XX wieku. Oprócz badań w zakresie teorii grafów dotyczących związku między właściwościami strukturalnymi i spektralnymi grafów, innym ważnym źródłem były badania w dziedzinie chemii kwantowej , ale powiązania między tymi dwoma kierunkami prac odkryto dopiero znacznie później. Monografia z 1980 roku Spectra of Graphs autorstwa Cvetkovića, Dooba i Sachsa podsumowała prawie wszystkie dotychczasowe badania w tej dziedzinie. W 1988 r. został zaktualizowany przez badanie Najnowsze wyniki w teorii widm grafów . Trzecie wydanie Spectra of Graphs (1995) zawiera podsumowanie dalszych ostatnich wkładów w ten temat. Dyskretna analiza geometryczna stworzona i opracowana przez Toshikazu Sunada w 2000 roku zajmuje się teorią grafów spektralnych w kategoriach dyskretnych Laplańczyków związanych z grafami ważonymi i znajduje zastosowanie w różnych dziedzinach, w tym w analizie kształtu . W ostatnich latach teoria grafów spektralnych rozszerzyła się na grafy o zmiennych wierzchołkach, często spotykane w wielu rzeczywistych zastosowaniach.

Zobacz też

• Silnie regularny wykres
• Łączność algebraiczna
• Algebraiczna teoria grafów
• Klastrowanie widmowe
• Analiza kształtu spektralnego
• Indeks Estrady
• Lovász theta
• Wykres ekspandera

Bibliografia

• Alona; Spencer (2011), Metoda probabilistyczna , Wiley.
• Brouwer, Andries ; Haemers, Willem H. (2011), Widma wykresów (PDF) , Springer
• Brawo; linial; Wigderson (2006), Wykresy ekspandera i ich zastosowania (PDF)

• Chung, Fan (1997). Amerykańskie Towarzystwo Matematyczne (red.). Teoria grafów spektralnych . Opatrzność, RI ISBN 0821803158. MR  1421568 [pierwsze 4 rozdziały dostępne na stronie]CS1 maint: postscript ( link )

• Schwenk, AJ (1973). „Prawie wszystkie drzewa są kospektralne”. W Harary, Frank (red.). Nowe kierunki w teorii grafów . Nowy Jork: Prasa akademicka . Numer ISBN 012324255X.

890297242 OCLC  .

Linki zewnętrzne

• Spielman, Daniel (2011). „Teoria grafów spektralnych” (PDF) . [rozdział z Kombinatorycznej Informatyki Naukowej]
• Spielman, Daniel (2007). „Teoria grafów spektralnych i jej zastosowania” . [prezentowane na konferencji FOCS 2007]
• Spielman, Daniel (2004). „Teoria grafów spektralnych i jej zastosowania” . [strona kursu i notatki do wykładu]