Algebraická teorie grafů - Algebraic graph theory

Vysoce symetrický graf, Petersenův graf, který je vrchol-tranzitivní, symetrický, vzdálenost-tranzitivní, a vzdálenost-pravidelná. Má to průměr 2. Jeho skupina automorfismu má 120 prvků a ve skutečnosti je symetrická skupina

{ displaystyle S_ {5}}

.

Algebraický teorie grafů je pobočkou matematika ve kterém algebraický metody jsou aplikovány na problémy o grafy. To je v rozporu s geometrický, kombinatorický nebo algoritmické přístupy. Existují tři hlavní větve algebraické teorie grafů, zahrnující použití lineární algebra, použití teorie skupin a studium grafové invarianty.

Větve algebraické teorie grafů

Pomocí lineární algebry

První větev algebraické teorie grafů zahrnuje studium grafů v souvislosti s lineární algebra. Zvláště studuje spektrum z matice sousedství, nebo Laplaciánská matice grafu (tato část algebraické teorie grafů se také nazývá teorie spektrálních grafů ). Pro Petersenův graf například spektrum matice sousedství je (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). Několik vět souvisí s vlastnostmi spektra s jinými vlastnosti grafu. Jako jednoduchý příklad, a připojeno graf s průměr D bude mít alespoň D+1 odlišné hodnoty v jeho spektru.^[1] Aspekty spektra grafů byla použita při analýze synchronizace z sítí.

Použití teorie grup

Druhá větev algebraické teorie grafů zahrnuje studium grafů v souvislosti s teorie skupin, zejména automorfické skupiny a teorie geometrických skupin. Důraz je kladen na různé rodiny grafů na základě symetrie (jako symetrické grafy, vertex-tranzitivní grafy, hranové tranzitivní grafy, vzdálenosti-tranzitivní grafy, vzdálenost-pravidelné grafy, a silně pravidelné grafy ) a na inkluzních vztazích mezi těmito rodinami. Některé z těchto kategorií grafů jsou natolik řídké seznamy grafů lze sestavit. Podle Fruchtova věta, Všechno skupiny lze reprezentovat jako skupinu automorfismu spojeného grafu (ve skutečnosti a kubický graf ).^[2] Další souvislost s teorií skupin spočívá v tom, že vzhledem k jakékoli skupině jsou symetrické grafy známé jako Cayleyovy grafy lze generovat a tyto mají vlastnosti související se strukturou skupiny.^[1]

A Cayleyův graf pro střídavá skupina A₄, tvořící a zkrácený čtyřstěn ve třech rozměrech. Všechny Cayleyovy grafy jsou vrchol-tranzitivní, ale některé vrcholové grafy (například Petersenův graf ) nejsou Cayleyovy grafy.

Správné vrcholové zbarvení Petersenův graf se 3 barvami, minimální možný počet. Podle chromatický polynom, existuje 120 takových barev se 3 barvami.

Tato druhá větev algebraické teorie grafů souvisí s první, protože vlastnosti symetrie grafu se odrážejí v jeho spektru. Zejména spektrum vysoce symetrického grafu, jako je Petersenův graf, má několik odlišných hodnot^[1] (Petersenův graf má 3, což je vzhledem k jeho průměru minimum). U Cayleyových grafů může spektrum souviset přímo se strukturou skupiny, zejména s její neredukovatelné znaky.^[1]^[3]

Studium invariantů grafů

A konečně, třetí větev teorie algebraických grafů se týká algebraických vlastností invarianty grafů, a zejména chromatický polynom, Tutteův polynom a uzlové invarianty. Chromatický polynom grafu například počítá jeho vlastní vrcholová barviva. Pro Petersenův graf je tento polynom ${ displaystyle t (t-1) (t-2) (t ^ {7} -12t ^ {6} + 67t ^ {5} -230t ^ {4} + 529t ^ {3} -814t ^ {2} + 775t-352)}$ .^[1] To zejména znamená, že Petersenův graf nelze správně obarvit jednou nebo dvěma barvami, ale lze jej obarvit 120 různými způsoby pomocí 3 barev. Hodně práce v této oblasti algebraické teorie grafů bylo motivováno pokusy dokázat čtyřbarevná věta. Stále je jich však mnoho otevřené problémy, jako je charakterizace grafů se stejným chromatickým polynomem a určení, které polynomy jsou chromatické.

Viz také

Reference

^ ^A ^b ^C ^d ^E Biggs, Norman (1993), Algebraická teorie grafů (2. vyd.), Cambridge: Cambridge University Press, ISBN 0-521-45897-8
^ R. Frucht. Grafy stupně 3 s danou abstraktní skupinou, kán. J. Math. 3 1949.
^ *Babai, L (1996), „Automorfické skupiny, izomorfismus, rekonstrukce“ v Graham, R; Grötschel, M; Lovász, L (eds.), Příručka kombinatoriky, Elsevier

Godsil, Chris; Royle, Gordone (2001), Algebraická teorie grafů, Postgraduální texty z matematiky, 207, New York: Springer-Verlag.

externí odkazy

Média související s Algebraická teorie grafů na Wikimedia Commons

[biggs-1] A ^b ^C ^d ^E Biggs, Norman (1993), Algebraická teorie grafů (2. vyd.), Cambridge: Cambridge University Press, ISBN 0-521-45897-8

[2] R. Frucht. Grafy stupně 3 s danou abstraktní skupinou, kán. J. Math. 3 1949.

[babai-3] *Babai, L (1996), „Automorfické skupiny, izomorfismus, rekonstrukce“ v Graham, R; Grötschel, M; Lovász, L (eds.), Příručka kombinatoriky, Elsevier

[1]

[2]

[3]

Skupiny grafů definované jejich automorfismy
vzdálenost-tranzitivní	→	vzdálenost-pravidelná	←	velmi pravidelné
↓
symetrický (oblouk-tranzitivní)	←	t-tranzitivní, $t \geq 2$		šikmo symetrický
↓
_{(je-li připojen)} vrchol a hrana-tranzitivní	→	hrana-tranzitivní a pravidelná	→	hrana tranzitivní
↓		↓		↓
vrchol-tranzitivní	→	pravidelný	→	_{(pokud je bipartitní)} biregular
↑
Cayleyův graf	←	nulově symetrický		asymetrický