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. 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.R. Frucht. Graphs of Degree 3 with given abstract group, Can. J. Math. 3 1949. 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.
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ó (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.*
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 . 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
Jegyzetek
.
További információk