Algebraisk grafteori

Algebraisk grafteori  är en riktning inom grafteorin som tillämpar algebraiska metoder på grafteoretiska problem (utöver geometriska , kombinatoriska och algoritmiska riktningar). I sin tur är algebraisk grafteori indelad i tre grenar: linjär-algebraisk , gruppteoretisk och att studera grafinvarianter .

Linjär algebra

En karakteristisk representant för den linjära algebraiska grenen är spektralgrafteorin , där spektra för närliggande matris eller Kirchhoff-matrisen för en graf studeras. För Petersen-grafen , till exempel, är spektrumet för den intilliggande matrisen (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). Vissa satser relaterar egenskaperna hos spektrumet till andra grafinvarianter . Som ett enkelt exempel kommer en sammankopplad graf med en diameter att ha åtminstone distinkta värden i sitt spektrum [1] . Grafspektrumegenskaper används för att analysera nätverkssynkronitet [ .

Gruppteori

Inom den gruppteoretiska grenen används metoder för allmän algebra och algebraisk kombinatorik , geometrisk gruppteori används i stor utsträckning ; en av de huvudsakliga konstruktionerna som studeras är grafautomorfismer (som bildar gruppen ). Uppmärksamhet ägnas åt olika familjer av grafer baserade på symmetri (som symmetriska grafer , vertextransitiva grafer , kanttransitiva grafer , distanstransitiva grafer , avståndsreguljära grafer och starkt regelbundna grafer ), och sambanden mellan dessa familjer. Vissa av dessa kategorier har ett litet antal grafer, så att de alla kan listas . Genom Fruchts teorem kan alla grupper representeras som automorfismgrupper av sammankopplade grafer (desutom kubiska grafer ) [2] . En annan koppling till gruppteorin är att givet vilken grupp som helst kan grafer som kallas Cayley-grafer bildas , och de har egenskaper relaterade till grafstruktur [1] .

Gruppgrenen är nära besläktad med den linjära algebraiska, eftersom en grafs symmetriegenskaper återspeglas i dess spektrum. Speciellt har spektrumet för en graf med hög symmetri, som Petersen-grafen, få distinkta egenvärden [1] (Petersen-grafen har 3 värden, vilket är det minsta möjliga talet för en graf med en diameter som Petersen Graf). För Cayley-grafer kan spektrumet relateras direkt till gruppens struktur, i synnerhet till dess irreducerbara representationer [1] [3] .

Graf invarianter

Algebraiska egenskaper hos grafinvarianter , såsom kromatiska polynom , Tatta-polynom , knutinvarianter , gör att man kan studera strukturen av grafer med algebraiska medel. Till exempel, det kromatiska polynomet i en graf, räknar antalet korrekta vertexfärgningar ; för Petersen-grafen är detta polynom:

[1] ,

i synnerhet innebär detta att Petersen-grafen inte kan färgas korrekt med en eller två färger, men med tre färger kan den färgas på 120 olika sätt. Mycket arbete på detta område är förknippat med försök att bevisa fyrfärgssatsen . Det finns många öppna frågor relaterade till invarianter, som att bestämma vilka grafer som har samma kromatiska polynom och vilka polynom som är kromatiska.

Se även

Anteckningar

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

Litteratur