Algebrallinen graafiteoria

Algebrallinen graafiteoria on graafiteorian  suunta, joka soveltaa algebrallisia menetelmiä graafiteoreettisiin ongelmiin ( geometristen , kombinatoristen ja algoritmisten suuntien lisäksi). Algebrallinen graafiteoria puolestaan ​​on jaettu kolmeen haaraan: lineaarialgebrallinen , ryhmäteoreettinen ja graafin invarianttien tutkiminen .

Lineaarinen algebra

Lineaarisen algebrallisen haaran tunnusomainen edustaja on spektrigraafiteoria , jossa tutkitaan graafin vierekkäisyysmatriisin tai Kirchhoff-matriisin spektrejä . Esimerkiksi Petersen-graafille viereisen matriisin spektri on (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). Jotkut lauseet yhdistävät spektrin ominaisuudet muihin graafiinvariantteihin . Yksinkertaisena esimerkkinä halkaisijaltaan yhdistetyllä graafilla on spektrissään ainakin erilliset arvot [1] . Graafispektrin ominaisuuksia käytetään verkon synkronisuuden analysointiin .

Ryhmäteoria

Ryhmäteoreettisella haaralla käytetään yleisalgebran ja algebrallisen kombinatoriikan menetelmiä, geometrista ryhmäteoriaa käytetään laajalti ; yksi tärkeimmistä tutkituista konstruktioista on graafiautomorfismit (muodostavat ryhmän ). Huomiota kiinnitetään erilaisiin symmetriaan perustuviin graafiperheisiin (kuten symmetriset graafit , kärkitransitiiviset graafit , reunatransitiiviset graafit , etäisyystransitiiviset graafit , etäisyyssäännölliset graafit ja vahvasti säännölliset graafit ) ja näiden perheiden välisiin yhteyksiin. Joissakin näistä luokista on pieni määrä kaavioita, jotta ne kaikki voidaan luetella . Fruchtin lauseen mukaan kaikki ryhmät voidaan esittää yhdistettyjen graafien (lisäksi kuutiograafien) automorfismiryhminä [ 2 ] . Toinen yhteys ryhmäteoriaan on se, että minkä tahansa ryhmän perusteella voidaan muodostaa Cayley-graafina tunnettuja graafeja ja niillä on graafirakenteeseen liittyviä ominaisuuksia [1] .

Ryhmähaara liittyy läheisesti lineaariseen algebralliseen, koska graafin symmetriaominaisuudet heijastuvat sen spektrissä. Erityisesti suuren symmetrian omaavan graafin, kuten Petersen-graafin, spektrillä on vähän erillisiä ominaisarvoja [1] (Petersen-graafissa on 3 arvoa, mikä on pienin mahdollinen luku sellaiselle graafille, jonka halkaisija on Petersenin kaltainen kaavio). Cayley-graafien tapauksessa spektri voidaan liittää suoraan ryhmän rakenteeseen, erityisesti sen redusoitumattomiin esityksiin [1] [3] .

Kuvaajan invariantit

Graafiinvarianttien algebralliset ominaisuudet , kuten kromaattiset polynomit , Tatta-polynomit , solmuinvariantit , mahdollistavat graafien rakenteen tutkimisen algebrallisin keinoin. Esimerkiksi graafin kromaattinen polynomi laskee sen oikeiden kärkiväritysten määrän ; Petersen-graafille tämä polynomi on:

[1] ,

Tämä tarkoittaa erityisesti sitä, että Petersen-graafia ei voi värjätä oikein yhdellä tai kahdella värillä, mutta kolmella värillä se voidaan värjätä 120 eri tavalla. Paljon työtä tällä alalla liittyy yrityksiin todistaa neljän värin lause . Invarianteihin liittyy monia avoimia kysymyksiä , kuten sen määrittäminen, millä graafilla on sama kromaattinen polynomi ja mitkä polynomit ovat kromaattisia.

Katso myös

Muistiinpanot

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

Kirjallisuus