Graafi invariant

Allikas: Vikipeedia

Graafi invariant on graafi struktuuri iseloomustava atribuudi arvuline väärtus või niisuguste väärtuste korrastatud kogum, mis ei sõltu graafi tippude märgistatusest ega selle graafilisest kujutisest. Mängib olulist osa graafide isomorfismi tuvastamisel.

Graafi invariandid jagunevad globaalseteks (graafi tervikut iseloomustavateks) ja lokaalseteks (näiteks, üksikuid tippe ja tipupaare iseloomustavateks).

Invariantide lihtsamaid näiteid[muuda | muuda lähteteksti]

  • Tippude arv või servade arv või mõlemad koos.
  • Graafi diameeter on lühima tee pikkus (kaugus) kahe omavahel kõige kaugema tipu vahel.
  • Sidusate komponentide arv .
  • Tippude minimaalne arv mille eemaldamine on tarvilik mittesidusa graafi saamiseks.
  • Servade minimaalne arv mille eemaldamine on tarvilik mittesidusa graafi saamiseks.
  • Seosmaatriksi determinant.
  • Seosmaatriksi karakteristlik polünoom.
  • Graafi orbiidid.
  • Hadwigeri arv .
  • Kromaatiline arv .
  • Wieneri indeks — suurus , kus on tippudevaheline väikseim kaugus и .
  • Randichi indeks — suurus .
  • Graafi spekter, mis saadakse seosmaatriksi alusel.

Invariantide arendusi[muuda | muuda lähteteksti]

Invariandina võib käsitleda mitte vaid üht konkreetset arvu vaid ka nende korteeži kujul , nagu selleks on:

  • Tippude valentsuste (astakute) vektor .
  • Polünoom ;
  • , kus on tippude arv valentsusega i.

Kahest või rohkemast parameetrist sõltuvaid invariantide süsteeme võib esitada formaalsete muutujate polünoomidena , nagu:

  • , kus on graafi alamgraafide arv, mis omavad tippu ja serva;
  • , kus on i tipuliste alamgraafide hulk, kus nõelte (st alamgraafi tippe graafi teiste tippudega siduvate servade) arv võrdub .

Selliseid invariante on arendatud hulgi, nende kokkulangemine on tarvilik kuid paraku mitte piisav tingimus isomorfismi olemasoluks.

Täielik invariant[muuda | muuda lähteteksti]

Invariant on täielik kui nende kokkulangevus on tarvilik ja piisav isomorfismi tuvastamiseks. Näiteks, igaüks väärtustest ja osutub fikseeritud tippude arvuga graafi täielikuks invariandiks.

Täielike invariantidena töötavad järgmised moodustised:

Algoritmilisest keerukusest[muuda | muuda lähteteksti]

Invariante eristatakse nende algoritmilise keerukuse alusel. Invariandid , , ja saadakse triviaalselt, samal ajal kui niisuguste invariantide nagu , , , , , puhul see nii ei ole.

Käesoleva aja ametlikust, XX sajandist pärit seisukohast, polünomiaalset täielikku invarianti ei tunnustata, kuigi pole tõestatud et neid ei esine. Samal ajal on näidatud, et semiootilise mudeli algoritmiline keerukus saab sõltuda vaid tippude arvust.

Kirjandust[muuda | muuda lähteteksti]

  • Harary, F. 1972 Graph Theory. Addison-Wesley ISBN 0201027879.
  • Зыков, А. А. 1987 Основы теории графов. Наука, Москва.
  • Dharwadker, A., Pirzada, B. 2011. Graph Theory, Amazon Books, 2011. ISBN 9781466254998