Teoria grafurilor spectrale

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 27 octombrie 2021; verificările necesită 2 modificări .

Teoria grafurilor spectrale  este o direcție în teoria grafurilor care studiază proprietățile grafurilor , polinoamelor caracteristice , vectorilor proprii și valorilor proprii ale matricelor asociate unui graf, cum ar fi matricea de adiacență a acestuia sau matricea Kirchhoff .

Un graf nedirecționat are o matrice de adiacență simetrică și, prin urmare, are valori proprii reale (al căror multiset se numește spectrul graficului ) și un set complet de vectori proprii .

În timp ce matricea de adiacență a unui grafic depinde de numerotarea vârfurilor, spectrul său este un invariant de grafic .

Teoria grafurilor spectrale se ocupă și de parametrii care sunt determinați prin înmulțirea valorilor proprii ale matricelor asociate cu graficul, cum ar fi numărul Colin de Verdière .

Grafice izospectrale

Se spune că două grafice sunt izospectrale sau cospectrale dacă matricele de adiacență ale graficelor au aceleași multiseturi de valori proprii.

Graficele izospectrale nu sunt neapărat izomorfe , dar graficele izomorfe sunt întotdeauna izospectrale. Perechea minimă de grafice ne-izomorfe cospectrale nedirecționate este , adică o stea cu cinci vârfuri și unirea unui ciclu cu 4 vârfuri și un grafic format dintr-un singur vârf, așa cum arată Kollatz și Singovich [1] [2] în 1957. Cea mai mică pereche de grafice poliedrice cospectrale non-izomorfe  sunt două enneaedre cu câte opt vârfuri [3] .

Aproape toți arborii au grafuri cospectrale față de ei, adică proporția de arbori de ordin , pentru fiecare dintre care există un graf cospectral, tinde spre 1 pe măsură ce crește [4] .

Graficele izospectrale sunt construite folosind metoda Sunada [5] .

Inegalitatea lui Cheeger

Celebra inegalitate Cheeger din geometria riemanniană are un analog discret folosind matricea Kirchhoff. Aceasta este poate cea mai importantă teoremă din teoria grafurilor spectrale și unul dintre cele mai utile fapte în aplicațiile algoritmice. Inegalitatea evaluează cea mai mică tăietură a graficului prin intermediul celei de-a doua valori proprii a matricei Kirchhoff.

constanta lui Cheeger

Constanta Cheeger (sau numărul Cheeger sau numărul izoperimetric ) a unui grafic  este o măsură numerică a faptului că un grafic are un blocaj. Constanta Cheeger ca măsură a prezenței unui blocaj este de mare interes în multe domenii. De exemplu, atunci când construiți rețele de computere puternic conectate , amestecați hărți și topologie cu dimensiuni joase (în special, atunci când studiați 3 - varietăți hiperbolice ).

În mod formal, constanta Cheeger a unui grafic cu vârfuri este definită ca

unde minimul este preluat peste toate mulțimile nevide, maximul cu vârfuri și este limita de muchie a mulțimii , adică mulțimea de muchii care au exact un vârf de capăt în [6] .

Inegalitatea lui Cheeger

Dacă graficul este -regular, există o legătură între și intervalul spectral al graficului . Inegalitatea lui Cheeger a fost studiată de Tanner, Alon și Milman [7] . Inegalitatea afirmă că [8]

Această inegalitate este strâns legată de limita Cheeger pentru lanțurile Markov și poate fi privită ca o versiune discretă a inegalității lui Cheeger în geometria riemanniană .

Istorie

Teoria grafurilor spectrale a apărut în anii 1950 și 1960. Monografia din 1980 „ Spectra of Graphs ” [9] de Cvetković, Michael Doob și Sachs a rezumat aproape toate cercetările în acest domeniu cunoscute până în acel moment. În 1988, a fost publicată o revizuire actualizată „ Recent Research in Graph Spectrum Theory ” [10] . A treia ediție a cărții Spectra of Graphs (1995) conține rezultatele contribuțiilor ulterioare în acest domeniu [11] .

Pe lângă studiile teoretice privind relația dintre proprietățile structurale și spectrale ale graficelor, studiile în chimia cuantică au devenit o altă sursă , dar relația dintre aceste două domenii a fost clarificată mult mai târziu [11] .

Vezi și

Note

  1. ↑ Collatz, L. și Sinogowitz, U. Spektren endlicher Grafen, Abh. Matematică. Sem. Univ. Hamburg. - 1957. - Nr. 21 . — S. 63–77 .
  2. ^ Weisstein, Eric W. Cospectral Graphs pe site- ul Wolfram MathWorld .  
  3. ↑ Haruo Hosoya, Umpei Nagashima, Sachiko Hyugaji. Grafice gemene topologice. Cea mai mică pereche de grafice poliedrice izospectrale cu opt vârfuri // Journal of Chemical Information and Modeling. - 1994. - T. 34 , nr. 2 . - S. 428-431 . - doi : 10.1021/ci00018a033 .
  4. ↑ AJ Schwenk. Aproape toți copacii sunt cospectrali // Direcții noi în teoria graficelor / F. Harary. - New York: Academic Press, 1973. - S. 275-307.
  5. ↑ Toshikazu Sunada. Acoperiri riemanniene și varietăți izospectrale // Ann. de Matematică. - 1985. - T. 21 . - S. 169-186 .
  6. ↑ Hoory, Linial, Widgerson, 2006 , Definiția 2.1.
  7. ↑ Alon, Spencer, 2011 .
  8. ↑ Hoory, Linial, Widgerson, 2006 , Teorema 2.4.
  9. ↑ Dragoš M. Cvetković, Michael Doob, Horst Sachs. Spectre de grafice. — 1980.
  10. ↑ Dragoš M. Cvetković, Michael Doob, Horst Sachs, A. Torgasev. Rezultate recente în teoria spectrelor grafice . - 1988. - (Analele matematicii discrete). — ISBN 0-444-70361-6 . Arhivat pe 5 noiembrie 2017 la Wayback Machine
  11. ↑ 1 2 Dragoš Cvetković, Peter Rowlinson, Slobodan Simić. Spații proprii ale graficelor. - 1997. - ISBN 0-521-57352-1 .

Literatură

Link -uri