Algebrai gráfelmélet

Az algebrai gráfelmélet a matematika egy ága, mely algebrai módszerekkel közelít meg gráfelméleti problémákat – szemben például a geometriai, kombinatorikai vagy algoritmikus megközelítésekkel. Az algebrai gráfelmélet három fő ága a lineáris algebrai módszereket, csoportelméletet felhasználó ágak és a gráftulajdonságok vizsgálata.

Az algebrai gráfelmélet diszciplínái

A lineáris algebra felhasználása

Az algebrai gráfelmélet egyik ága a lineáris algebra módszereivel vizsgálja a gráfokat. Ide tartozik a szomszédsági mátrix vagy a gráf Laplace-mátrixa sajátérték-felbontása (avagy spektruma – ezt az alterületet szokás spektrális gráfelméletnek is nevezni). Például a Petersen-gráf szomszédságának spektruma (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). Több olyan matematikai tétel van, ami a spektrum tulajdonságait más gráftulajdonságokkal köti össze. Ilyen például, hogy egy legalább D átmérőjű összefüggő gráf spektrumában legalább D+1 különböző érték szerepel.^[1] A gráf spektrumának egyes aspektusait felhasználták a hálózatok szinkronizálhatóságának analízisében.

A csoportelmélet felhasználása

Az algebrai gráfelmélet másik ága csoportelméleti keretekben vizsgálja a gráfokat, különösen az automorfizmus-csoportok és a geometriai csoportelmélet tekintetében. A fókusz a különböző szimmetriák által definiált gráfcsaládokon (mint szimmetrikus gráfok, csúcstranzitív gráfok, éltranzitív gráfok, távolságtranzitív gráfok, távolságreguláris gráfok és erősen reguláris gráfok) és a családok közti inkluzív kapcsolatokon van. Ezek a kategóriák néha kellően ritkák ahhoz, hogy a gráfok listázhatók legyenek. A Frucht-tétel alapján minden csoport kifejezhető egy összefüggő gráf (sőt, 3-reguláris gráf) automorfizmus-csoportjaként.^[2] A csoportelmélettel való másik kapcsolat szerint bármely csoporthoz generálhatók szimmetrikus, ún. Cayley-gráfok, melyek tulajdonságai rokonságot mutatnak a csoport szerkezetével.^[1]

Az A₄ alternáló csoport Cayley-gráfja, ami három dimenzióban egy csonkított tetraédert alkot. Minden Cayley-gráf csúcstranzitív, de nem minden csúcstranzitív gráf Cayley-gráf (például a Petersen-gráf sem az).

Az algebrai gráfelmélet második ága kapcsolódik az elsőhöz, hiszen a gráf szimmetriatulajdonságai megjelennek a gráf spektrumában is. Az erősen szimmetrikus gráfok, mint a Petersen-gráf, spektrumában kevés különböző érték található^[1] (a Petersen-gráf esetén csak 3, ami adott átmérő mellett a minimális érték). A Cayley-gráfok spektruma közvetlenül kapcsolódik a csoport szerkezetéhez, különösen annak irreducibilis karaktereihez.^[1]^[3]

Gráfinvariánsok tanulmányozása

Végül az algebrai gráfelmélet harmadik ága a gráfok invariánsainak algebrai tulajdonságaival foglalkozik, különösen a kromatikus polinommal, a Tutte-polinommal és a csomóinvariánsokkal. Egy gráf kromatikus polinomja a gráf jó csúcsszínezéseit számolja meg. A Petersen-gráf esetében ez a polinom $t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$ .^[1] Ebben az esetben ez azt jelenti, hogy a Petersen-gráf nem jól színezhető egy vagy két színnel, három színnel viszont 120-féleképpen is. Ennek a területnek a fejlődését nagyban motiválták a négyszínsejtés bizonyítási kísérletei. Azóta is sok nyitott kérdés van a gráfszínezés területén, például az azonos kromatikus számú gráfok karakterizálása, illetve annak eldöntése, hogy adott polinom lehet-e egy gráf kromatikus polinomja.

Kapcsolódó szócikkek

Fordítás

Ez a szócikk részben vagy egészben az Algebraic graph theory című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

↑ ^a ^b ^c ^d ^e Biggs, Norman (1993), Algebraic Graph Theory (2nd ed.), Cambridge: Cambridge University Press, ISBN 0-521-45897-8
↑ R. Frucht. Graphs of Degree 3 with given abstract group, Can. J. Math. 3 1949.
↑ *Babai, L (1996), "Automorphism groups, isomorphism, reconstruction", in Graham, R; Grötschel, M & Lovász, L, Handbook of Combinatorics, Elsevier

Godsil, Chris & Royle, Gordon (2001), Algebraic Graph Theory, vol. 207, Graduate Texts in Mathematics, New York: Springer-Verlag.

További információk

A Wikimédia Commons tartalmaz Algebrai gráfelmélet témájú kategóriát.

[biggs-1] Biggs, Norman (1993), Algebraic Graph Theory (2nd ed.), Cambridge: Cambridge University Press, ISBN 0-521-45897-8

[2] R. Frucht. Graphs of Degree 3 with given abstract group, Can. J. Math. 3 1949.

[babai-3] *Babai, L (1996), "Automorphism groups, isomorphism, reconstruction", in Graham, R; Grötschel, M & Lovász, L, Handbook of Combinatorics, Elsevier

[1]

[2]

[3]

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitív	${\boldsymbol {\rightarrow }}$	távolságreguláris	${\boldsymbol {\leftarrow }}$	erősen reguláris
${\boldsymbol {\downarrow }}$
szimmetrikus	${\boldsymbol {\leftarrow }}$	t-tranzitív, t ≥ 2		ferdeszimmetrikus
${\boldsymbol {\downarrow }}$
_{(ha összefüggő)} csúcs- és éltranzitív	${\boldsymbol {\rightarrow }}$	éltranzitív és reguláris	${\boldsymbol {\rightarrow }}$	éltranzitív
${\boldsymbol {\downarrow }}$		${\boldsymbol {\downarrow }}$		${\boldsymbol {\downarrow }}$
csúcstranzitív	${\boldsymbol {\rightarrow }}$	reguláris	${\boldsymbol {\rightarrow }}$	_(ha páros) bireguláris
${\boldsymbol {\uparrow }}$
Cayley-gráf	${\boldsymbol {\leftarrow }}$	zérószimmetrikus		aszimmetrikus