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 erősen szimmetrikus Petersen-gráf, egyszerre csúcstranzitív, szimmetrikus, távolságtranzitív és távolságreguláris. Átmérője 2. Automorfizmuscsoportja 120 elemű, és megegyezik az ${\displaystyle S_{5}}$ szimmetrikus csoporttal.

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

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

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).

A Petersen-gráf 3-színezése (kevesebb színnel nem lehetséges jó színezés). A kromatikus polinom szerint 120-féle 3-színezés lehetséges.

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 ${\displaystyle 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

• Spektrális gráfelmélet
• Algebrai összefüggőség
• Dulmage–Mendelsohn-felbontás
• Gráftulajdonság
• Szomszédsági mátrix

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

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

• .

További információk

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