Algebraická teorie grafů

Algebraická teorie grafů  je směr v teorii grafů , který aplikuje algebraické metody na grafově teoretické problémy (kromě geometrických , kombinatorických a algoritmických směrů). Algebraická teorie grafů je zase rozdělena do tří větví: lineárně-algebraická , grupová a studující invarianty grafů .

Lineární algebra

Charakteristickým představitelem lineární algebraické větve je spektrální teorie grafů , ve které jsou studována spektra matice sousednosti nebo Kirchhoffova matice grafu. Pro Petersenův graf je například spektrum sousední matice (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). Některé věty spojují vlastnosti spektra s jinými invarianty grafu . Jako jednoduchý příklad, souvislý graf s průměrem bude mít ve svém spektru alespoň odlišné hodnoty [1] . Vlastnosti spektra grafu se používají k analýze synchronicity sítě .

Teorie grup

V oboru teorie grup se používají metody obecné algebry a algebraické kombinatoriky , široce se využívá teorie geometrických grup ; jednou z hlavních studovaných konstrukcí jsou grafové automorfismy (tvořící grupu ). Pozornost je věnována různým rodinám grafů založených na symetrii (jako jsou symetrické grafy , vertex-tranzitivní grafy , hraně-tranzitivní grafy , vzdálenostně-tranzitivní grafy , vzdálenostně-regulární grafy a silně regulární grafy ) a souvislostem mezi těmito rodinami. Některé z těchto kategorií mají malý počet grafů, takže je lze vypsat všechny . Podle Fruchtovy věty lze všechny grupy reprezentovat jako skupiny automorfismu souvislých grafů (navíc kubické grafy ) [2] . Další spojení s teorií grup spočívá v tom, že při dané grupě lze vytvořit grafy známé jako Cayleyovy grafy , které mají vlastnosti související se strukturou grafu [1] .

Skupinová větev úzce souvisí s lineární algebraickou, protože symetrické vlastnosti grafu se odrážejí v jeho spektru. Zejména spektrum grafu s vysokou symetrií, jako je Petersenův graf, má málo odlišných vlastních hodnot [1] (Petersenův graf má 3 hodnoty, což je nejmenší možné číslo pro graf s průměrem jako Petersenův graf. graf). U Cayleyových grafů může spektrum přímo souviset se strukturou skupiny, zejména s jejími neredukovatelnými reprezentacemi [1] [3] .

Grafové invarianty

Algebraické vlastnosti invariantů grafu , jako jsou chromatické polynomy , Tatta polynomy , invarianty uzlů , umožňují studovat strukturu grafů algebraickými prostředky. Například chromatický polynom grafu počítá počet jeho správných zabarvení vrcholů ; pro Petersenův graf je tento polynom:

[1] ,

konkrétně to znamená, že Petersenův graf nelze správně obarvit jednou nebo dvěma barvami, ale třemi barvami jej lze vybarvit 120 různými způsoby. Mnoho práce v této oblasti je spojeno s pokusy dokázat větu o čtyřech barvách . Existuje mnoho otevřených otázek souvisejících s invarianty, jako je určení, které grafy mají stejný chromatický polynom a které polynomy jsou chromatické.

Viz také

Poznámky

  1. ↑ 1 2 3 4 5 Biggs, 1993 .
  2. ↑ Frucht, 1949 .
  3. ↑ Babai, 1996 .

Literatura