Servagraaf

Allikas: Vikipeedia

Servagraaf E(G) on lihtgraafi G teisend kus tippudeks on graafi G servad, mis on tippudena naabrid graafis E(G) vaid siis kui need on servadena naabrid graafis G.

Graafi servagraafi mõiste on iseenesest lihtne ning selle avastajaid ja nimepanijaid on mitu. Viimane neist oli Frank Harary, kelle poolt antud ingliskeelne nimetus line graph on jäänud püsima.

Üheksa väiseimat graafi, mis ei rahulda servagraafiks olemise tingimust. Neid nimetatakse keelatud graafideks. Graaf on servagraaf parajasti siis, kui see ei sisalda ühtegi keelatud graafi kujutavat alamgraafi.

Graaf G on mingi teise graafi servagraaf E(H) siis ja ainult siis, kui graafis G esineb niisugune kliki-kogum, kus G iga tipp kuulub täpselt kahte klikki.

Kirjandus[muuda | redigeeri lähteteksti]