Spektrální teorie grafů - Spectral graph theory
v matematika, spektrální teorie grafů je studium vlastností a graf ve vztahu k charakteristický polynom, vlastní čísla, a vlastní vektory matic spojených s grafem, například jeho matice sousedství nebo Laplaciánská matice.
Matice sousedství a jednoduchý graf je nemovitý symetrická matice a proto je ortogonálně úhlopříčně; jeho vlastní čísla jsou skutečná algebraická celá čísla.
Zatímco matice sousedství závisí na označení vrcholů, její spektrum je graf neměnný, i když ne úplný.
Teorie spektrálního grafu se také zabývá parametry grafu, které jsou definovány pomocí multiplikácií vlastních čísel matic spojených s grafem, jako je například Colin de Verdière číslo.
Cospectral grafy
Nazývají se dva grafy cospectral nebo isospektrální pokud jsou matice sousedství grafů stejné multisety vlastních čísel.

Cospektrální grafy nemusí být izomorfní, ale izomorfní grafy jsou vždy cospectral.
Grafy určené jejich spektrem
Graf se říká, že je určen jeho spektrem, pokud existuje jakýkoli jiný graf se stejným spektrem jako je izomorfní s .
Některé první příklady rodin grafů, které jsou určeny jejich spektrem, zahrnují:
- The kompletní grafy.
- Konečný hvězdné stromy.
Cospectral kamarádi
O dvojici grafů se říká, že jsou cospectral kamarádi, pokud mají stejné spektrum, ale nejsou izomorfní.
Nejmenší pár cospectral kamarádů je {K.1,4, C4 ∪ K.1}, zahrnující 5-vrchol hvězda a grafová unie 4-vrcholu cyklus a graf s jedním vrcholem, jak uvádí Collatz a Sinogowitz[1][2] v roce 1957.
Nejmenší pár mnohostěnný cospectral kamarádi jsou enneahedra s osmi vrcholy.[3]
Hledání cospectral grafů
Téměř všechny stromy jsou cospectral, tj. jak roste počet vrcholů, zlomek stromů, pro které existuje cospectral strom, jde na 1.[4]
Pár pravidelné grafy jsou cospectral právě tehdy, jsou-li jejich doplňky cospectral.[5]
Pár vzdálenost-pravidelné grafy jsou cospectral právě tehdy, pokud mají stejné průnikové pole.
Cospectral grafy mohou být také konstruovány pomocí Sunada metoda.[6]
Dalším důležitým zdrojem cospectral graphs are the point-collinearity graphs and the line-intersection graphs of geometrie bodové čáry. Tyto grafy jsou vždy cospectral, ale jsou často non-izomorfní.[7]
Cheegerova nerovnost
Známý Cheegerova nerovnost z Riemannova geometrie má diskrétní analog zahrnující lalaciánskou matici; toto je možná nejdůležitější věta ve spektrální teorii grafů a jedno z nejužitečnějších faktů v algoritmických aplikacích. Přibližuje nejmenší výřez grafu prostřednictvím druhé vlastní hodnoty jeho Laplacian.
Cheegerova konstanta
The Cheegerova konstanta (taky Cheegerovo číslo nebo izoperimetrické číslo) a graf je číselná míra toho, zda má graf „úzké místo“. Cheegerova konstanta jako měřítko „úzkého profilu“ má velký zájem v mnoha oblastech: například budování dobře propojených počítačové sítě, míchání karet, a nízkodimenzionální topologie (zejména studie hyperbolický 3-rozdělovače ).
Formálněji Cheegerova konstanta h(G) grafu G na n vrcholy je definován jako
kde minimum přesahuje všechny neprázdné sady S maximálně n/ 2 vrcholy a ∂ (S) je hraniční hranice z S, tj. sada hran s přesně jedním koncovým bodem S.[8]
Cheegerova nerovnost
Když graf G je d-pravidelný, existuje vztah mezi h(G) a spektrální mezera d - λ2 z G. Nerovnost kvůli Dodziukovi[9] a nezávisle Alon a Milmane[10] tvrdí, že[11]
Tato nerovnost úzce souvisí s Cheeger vázán pro Markovovy řetězy a lze jej považovat za diskrétní verzi Cheegerova nerovnost v Riemannova geometrie.
Hoffman-Delsarteova nerovnost
Existuje vlastní číslo vázané na nezávislé sady v pravidelné grafy, původně kvůli Alan J. Hoffman a Philippe Delsarte.[12]
Předpokládejme to je -pravidelný graf na vrcholy s nejmenším vlastním číslem . Pak:
Tato vazba byla použita pro stanovení např. algebraické důkazy Erdős – Ko – Radova věta a jeho analog pro protínající se rodiny podprostorů konečná pole.[13]
Historický obrys
Teorie spektrálních grafů se objevila v 50. a 60. letech. kromě teoretická graf výzkum vztahu mezi strukturálními a spektrálními vlastnostmi grafů, dalším významným zdrojem byl výzkum v kvantová chemie, ale souvislosti mezi těmito dvěma liniemi práce byly objeveny až mnohem později.[14] Monografie z roku 1980 Spektrum grafů[15] Cvetković, Doob a Sachs shrnuli téměř veškerý dosavadní výzkum v této oblasti. V roce 1988 byl průzkumem aktualizován Nedávné výsledky v teorii grafového spektra.[16] 3. vydání Spektra grafů (1995) obsahuje souhrn dalších nedávných příspěvků k tématu.[14] Diskrétní geometrická analýza vytvořená a vyvinutá Toshikazu Sunada v roce 2000 se zabývá spektrální teorií grafů, pokud jde o jednotlivé Laplaciany spojené s váženými grafy,[17] a najde uplatnění v různých oblastech, včetně tvarová analýza. V posledních letech se teorie spektrálních grafů rozšířila na vrcholově proměnné grafy, s nimiž se často setkáváme v mnoha aplikacích v reálném životě.[18][19][20][21]
Viz také
- Silně pravidelný graf
- Algebraická konektivita
- Algebraická teorie grafů
- Spektrální shlukování
- Spektrální tvarová analýza
- Estrada index
- Lovász theta
- Expander graf
Reference
- ^ Collatz, L. a Sinogowitz, U. "Spektren endlicher Grafen." Abh. Matematika. Sem. Univ. Hamburk 21, 63–77, 1957.
- ^ Weisstein, Eric W. "Cospectral Graphs". MathWorld.
- ^ Hosoya, Haruo; Nagashima, Umpei; Hyugaji, Sachiko (1994), "Topologické dvojité grafy. Nejmenší pár isospektrálních polyedrických grafů s osmi vrcholy", Journal of Chemical Information and Modeling, 34 (2): 428–431, doi:10.1021 / ci00018a033.
- ^ Schwenk (1973), str. 275-307.
- ^ Godsil, Chris (7. listopadu 2007). „Jsou téměř všechny grafy spektrální?“ (PDF).
- ^ Sunada, Toshikazu (1985), „Riemannovy krytiny a isospektrální varietá“, Ann. matematiky., 121 (1): 169–186, doi:10.2307/1971195, JSTOR 1971195.
- ^ Viz (Brouwer & Haemers 2011 ) v externí odkazy.
- ^ Definice 2.1 v Hoory, Linial & Widgerson (2006)
- ^ J.Dodziuk, Diferenční rovnice, izoperimetrická nerovnost a pomíjivost určitých náhodných procházek, Trans. Amer. Matematika. Soc. 284 (1984), č. 2. 2, 787-794.
- ^ Alon & Spencer 2011.
- ^ Věta 2,4 palce Hoory, Linial & Widgerson (2006)
- ^ Godsil, Chris (květen 2009). „Věty Erdős-Ko-Rado“ (PDF).
- ^ 1949-, Godsil, C. D. (Christopher David) (2016). Erdős-Ko-Rado věty: algebraické přístupy. Meagher, Karen (vysokoškolská učitelka). Cambridge, Velká Británie. ISBN 9781107128446. OCLC 935456305.CS1 maint: číselné názvy: seznam autorů (odkaz)
- ^ A b Vlastní prostory grafůtím, že Dragoš Cvetković, Peter Rowlinson, Slobodan Simić (1997) ISBN 0-521-57352-1
- ^ Dragoš M. Cvetković, Michael Doob, Horst Sachs, Spektra grafů (1980)
- ^ Cvetković, Dragoš M .; Doob, Michael; Gutman, Ivan; Torgasev, A. (1988). Nedávné výsledky v teorii grafového spektra. Letopisy diskrétní matematiky. ISBN 0-444-70361-6.
- ^ Sunada, Toshikazu (2008), „Diskrétní geometrická analýza“, Proceedings of Symposia in Pure Mathematics, 77: 51–86, doi:10.1090 / pspum / 077/2459864, ISBN 9780821844717.
- ^ Šuman, David I.; Ricaud, Benjamin; Vandergheynst, Pierre (březen 2016). "Vrcholně-frekvenční analýza na grafech". Aplikovaná a výpočetní harmonická analýza. 40 (2): 260–291. arXiv:1307.5708. doi:10.1016 / j.acha.2015.02.005. ISSN 1063-5203.
- ^ Stankovic, Ljubisa; Dakovic, Miloš; Sejdic, Ervin (červenec 2017). „Vertex-Frequency Analysis: A Way to Local Graph Spectral Components [Lecture Notes]“. IEEE Signal Processing Magazine. 34 (4): 176–182. Bibcode:2017ISPM ... 34..176S. doi:10.1109 / msp.2017.2696572. ISSN 1053-5888.
- ^ Sakiyama, Akie; Watanabe, Kana; Tanaka, Yuichi (září 2016). Msgstr "Vlny spektrálního grafu a banky filtrů s chybou nízké aproximace". Transakce IEEE na zpracování signálu a informací v sítích. 2 (3): 230–245. doi:10.1109 / tsipn.2016.2581303. ISSN 2373-776X.
- ^ Behjat, Hamid; Richter, Ulrike; Van De Ville, Dimitri; Sornmo, Leif (15. 11. 2016). „Signálně přizpůsobené těsné rámečky na grafech“. Transakce IEEE při zpracování signálu. 64 (22): 6017–6029. Bibcode:2016ITSP ... 64,6017B. doi:10.1109 / tsp.2016.2591513. ISSN 1053-587X.
- Schwenk, A. J. (1973). „Téměř všechny stromy jsou kosovské“. v Harary, Franku (vyd.). Nové směry v teorii grafů. New York: Akademický tisk. ISBN 012324255X. OCLC 890297242.CS1 maint: ref = harv (odkaz)
Další čtení
- Chung, Fan (1997). Americká matematická společnost (ed.). Teorie spektrálního grafu. Providence, R. I. ISBN 0821803158. PAN 1421568 [první 4 kapitoly jsou k dispozici na webu]
externí odkazy
- Brouwer, Andries; Haemers, Willem H. (2011). „Spectra of Graphs“ (PDF).CS1 maint: ref = harv (odkaz)
- Spielman, Daniel (2011). „Teorie spektrálního grafu“ (PDF). [kapitola z kombinatorických vědeckých výpočtů]
- Spielman, Daniel (2007). „Teorie spektrálního grafu a její aplikace“. [představeno na konferenci FOCS 2007]
- Spielman, Daniel (2004). „Teorie spektrálního grafu a její aplikace“. [stránka kurzu a poznámky k přednášce]