Algebrai gráfelmélet

Az algebrai gráfelmélet a gráfelmélet  olyan iránya, amely algebrai módszereket alkalmaz gráfelméleti problémákra (a geometriai mellett kombinatorikus és algoritmikus irányok). Az algebrai gráfelmélet viszont három ágra oszlik: lineáris-algebrai , csoportelméleti és gráfinvariánsok tanulmányozására .

Lineáris algebra

A lineáris algebrai ág jellegzetes képviselője a spektrális gráfelmélet , amelyben egy gráf szomszédsági mátrixának vagy Kirchhoff -mátrixának spektrumait vizsgálják. Például a Petersen-gráf esetében a szomszédos mátrix spektruma (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). Egyes tételek a spektrum tulajdonságait más gráfinvariánsokhoz kapcsolják . Egyszerű példaként egy átmérőjű összekapcsolt gráfnak legalább külön értékei lesznek a spektrumában [1] . A gráf spektrum tulajdonságait a hálózati szinkronitás elemzésére használják .

Csoportelmélet

A csoportelméleti ágban az általános algebra és az algebrai kombinatorika módszereit használják, a geometriai csoportelméletet széles körben használják ; az egyik fő vizsgált konstrukció a gráf automorfizmusok ( a csoportot alkotva ). Figyelmet fordítanak a szimmetrián alapuló különféle gráfcsaládokra (például szimmetrikus gráfokra , csúcstranzitív gráfokra , éltranzitív gráfokra , távolság-tranzitív gráfokra , távolság-reguláris gráfokra és erősen szabályos gráfokra ), valamint a családok közötti kapcsolatokra. E kategóriák némelyike ​​kis számú grafikonnal rendelkezik, így mindegyik listázható . Frucht tétele szerint minden csoport összefüggő gráfok (sőt köbgráfok) automorfizmuscsoportjaként ábrázolható [ 2] . Egy másik kapcsolat a csoportelmélettel, hogy bármely csoportból Cayley-gráfokként ismert gráfok képezhetők , és a gráfszerkezettel kapcsolatos tulajdonságokkal rendelkeznek [1] .

A csoportág szorosan összefügg a lineáris algebraival, mivel a gráf szimmetriatulajdonságai tükröződnek a spektrumában. Különösen egy nagy szimmetriájú gráf spektruma, mint például a Petersen-gráf, kevés különálló sajátértékkel rendelkezik [1] (a Petersen-gráfnak 3 értéke van, ami a lehető legkisebb szám egy olyan átmérőjű gráf esetében, mint a Petersen-gráf grafikon). A Cayley-gráfok esetében a spektrum közvetlenül kapcsolatba hozható a csoport szerkezetével, különösen annak irreducibilis reprezentációival [1] [3] .

Grafikonvariánsok

A gráfinvariánsok algebrai tulajdonságai , mint például a kromatikus polinomok , a Tatta-polinomok , a csomóinvariánsok , lehetővé teszik a gráfok szerkezetének algebrai eszközökkel történő tanulmányozását. Például egy gráf kromatikus polinomja megszámolja a helyes csúcsszínezések számát ; a Petersen-gráf esetében ez a polinom:

[1] ,

Ez konkrétan azt jelenti, hogy a Petersen-gráf nem színezhető helyesen egy vagy két színnel, de három színnel 120 különböző módon színezhető. Ezen a területen sok munka kapcsolódik a négy szín tételének bizonyítására . Sok nyitott kérdés van az invariánsokkal kapcsolatban, például annak meghatározása, hogy mely gráfokon van ugyanaz a kromatikus polinom, és mely polinomok kromatikusak.

Lásd még

Jegyzetek

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

Irodalom