Egy struktúra vizsgálatának klasszikus megközelítési módja, hogy numerikus „invariánsait” határozzuk meg. Megfelelően választott invariánsokkal, a tekintett probléma elvileg áttranszformálható numerikus, vagy algebrai problémává, és így a klasszikus algebrában már régóta kidolgozott, hatékony módszerek kaphatnak szerepet.
Az előző fejezetekben tekintett invariánsokat (összefüggőség, kromatikus szám, kromatikus polinom) kombinatorikusan definiáltuk, és az algebrai tulajdonságaiknak nem volt komoly szerepe. Másrészt, amikor bevezetjük egy gráf spektrumát, ami az adjacenciamátrixának a spektruma, akkor egy algebrailag definiált invariánsrendszerhez jutunk. Általában a spektrum nem jellemzi egyértelműen a gráfot, ugyanakkor igen sok érdekes gráftulajdonsággal van kapcsolatban és folytonosan újabb és újabb összefüggések felfedezésére kerül sor a kutatások során. Bár a gráf spektrumának bevezetése nem egy univerzális módszer, hogy minden problémát ennek segítségével meg tudnánk oldani, de rendkívül hatékonynak bizonyul tisztán gráfelméleti kérdésekben (például, az erősen reguláris gráfok osztályozásában).
A spektrum hatásos használata a gráfelméleti vizsgálatokban azon múlik, hogy képesek vagyunk-e megtenni két lényeges lépést. Először is, hogy gráfok egy széles osztályának a spektrumát ki kell tudjuk számítani (vagy, általánosabban, képesnek kell lennünk arra, hogy gráfelméleti információkat lefordítsunk spektrális információkra), és másodszor, képesnek kell lennünk, hogy gráfok tulajdonságait a spektrális tulajdonságokból vezessük le. Érdekes, hogy igen széles azon módszerek skálája, melyek a gráfokat a spektrumukkal hozzák kapcsolatba, mindkét értelemben.
Az összefüggések egy bizonyos hányada sporadikus; de bizonyos sajátértékek nyilvánvalóan összefüggenek kombinatorikus tulajdonságokkal. Így például, a legnagyobb sajátérték az élsűrűséggel van kapcsolatban; a második legnagyobb, a „globális összefüggőséggel”, vagy konduktanciával (vezetőképességgel); a legkisebb sajátértékek némelyike pedig a kromatikus számmal függ össze. A vezetőképesség ugyanakkor, szorosan összefügg a gráfon tett véletlen sétával. Erre mutatunk egy gyakorlatsorozatot.
* * * |
A gráf spektrumának néhány tulajdonsága a nem negatív
mátrixok Frobenius–Perron-féle elméletének speciális következménye.
Bizonyítás és hivatkozás nélkül fogjuk használni a következő
tényeket (lásd például F. R. Gantmacher, Applications of
the Theory of Matrices, Interscience, 1959, vagy H. Minc,
Non-negative Matrices, Wiley–Interscience, 1988). Tetszőleges
Hacsak másképp nem szükséges, ebben a fejezetben feltesszük,
hogy
Határozzuk meg a következő gráfok spektrumát, és a
hozzájuk tartozó sajátvektoraikat;
Tegyük fel, hogy ismerjük egy reguláris gráf spektrumát. Határozzuk meg a következő gráfok spektrumát:
(a) a komplementernek,
(b) az élgráfjának,
(c) Mi a spektruma a Petersen-gráfnak (9. ábra)?
Legyen
Legyen
Legyen
(a)
(b)
(c) Határozzuk meg
(d) Határozzuk meg a
Adjunk meg végtelen sok nemizomorf fapárt, melyeknek ugyanaz a spektruma.
Tegyük fel, hogy
(a)
(b) a
Legyen
a
Határozzuk meg az
Legyen
Ha a páros
Ha a 3-reguláris
Ha
(a) Legyen
Mely összefüggő gráfokra teljesül, hogy
(b) Ha
(c) Ha
Mutassuk meg, hogy tetszőleges
Tegyük fel, hogy
Legyen a
Legyenek
(a) Egy összefüggő
(b) Egy gráf akkor és csak akkor páros, ha a spektruma szimmetrikus az origóra.
Legyen
(a) Legyenek
(b) Mutassuk meg, hogy ha a
Legyen
Bizonyítsuk be, hogy minden
Tegyük fel, hogy
Egy összefüggő gráf különböző sajátértékeinek a száma nagyobb, mint az átmérője.
Adott
ha
Egy projektív sík
Az egyszerű
(i) minden pont foka
(ii) minden pontpárhoz pontosan
(a) Határozzuk meg
(b) Határozzuk meg az összes ilyen gráfot, ha
(c) Keressünk végtelen sok nem-triviális példát ilyen gráfokra (triviális példa a teljes gráf).
(a) Legyen
(b) Ha
Legyen
Legyen
(a) Bizonyítsuk be, hogy
(b)* Bizonyítsuk be, hogy
(a) Legyen
(b) Legyen
(a) Legyen
(b) Bizonyítsuk be, hogy legalább 95% valószínűséggel, a
* * * |
A fejezet hátralevő részében legyen
Fejezzük ki
(a) Keressünk
(b) Bizonyítsuk be, hogy a stacionárius eloszlás egyértelmű.
(c) Ha
Ha
Jelölje
(a)
(b)
(a) Azon lépések várható száma, amikor egy
(b) Azon lépések várható száma mielőtt egy
Keressük meg a
(a) Mutassuk meg egy példán, hogy az elérési idő
(b) Ha
Annak a valószínűsége, hogy egy
(a)* Bizonyítsuk be, hogy tetszőleges három
(b) Bizonyítsuk be, hogy tetszőleges gráf pontjai
elrendezhetők úgy, hogy ha
A menettérti idő tetszőleges két,
Jelölje
(a) Bizonyítsuk be az
(b) Adjunk egy új bizonyítást 11.38(a)-ra, (a)-ra alapozva.
(c)* Ha
ahol
(a) Használjuk fel 11.44(c)-t 11.42(a) egy új bizonyításához.
(b) Határozzuk meg (aszimptotikusan) a
(a) Keressünk egy formulát a menettérti időre, mely analóg 11.44(c)-vel.
(b) Bizonyítsuk be, hogy a
(a) Határozzuk meg
(b) A fedési idő, tetszőleges gráf, tetszőleges pontjából
indulva, legfeljebb
(a) Jelölje
(b) Legyen
A fedési idő (tetszőleges pontból) legfeljebb
Legyen
Tekintsünk egy véletlen sétát a
[Vessük össze ezt az időkorlátot azzal a ténnyel, hogy a
(a) Legyen
minden
(b) Tekintsük a
(c) Tekintsük a
(d) Minden
(a) Ha
(b) Keressünk egy hasonló összefüggést a menettérti idő, és a 11.52(c)-beli rugós modellbeli erők és energiák között.
(c) Jelölje
Egy
Legyen
(a) Bizonyítsuk be, hogy a menettérti idő
(b) Mutassuk meg egy példán, hogy hasonló állítás nem teljesül az elérési időre.
(c) Ha
Legyen
(a) Az
(b)* Az
(c)* Az
Jelölje
(a) Bizonyítsuk be, hogy ha
(b) Ha
(c) Tegyük fel, hogy minden
Tekintsünk egy
Legyen
Bizonyítsuk be, hogy minden