Algebrai gráfelmélet
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/91/Petersen1_tiny.svg/200px-Petersen1_tiny.svg.png)
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
[szerkesztés]A lineáris algebra felhasználása
[szerkesztés]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
[szerkesztés]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]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0f/TruncatedTetrahedron.gif/220px-TruncatedTetrahedron.gif)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/90/Petersen_graph_3-coloring.svg/200px-Petersen_graph_3-coloring.svg.png)
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
[szerkesztés]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 .[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
[szerkesztés]- 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
[szerkeszté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
[szerkesztés]- ↑ 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
[szerkesztés]A Wikimédia Commons tartalmaz Algebrai gráfelmélet témájú kategóriát.