Servagraaf

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.

• 
  Graaf G
• 
  E(G) tipud kujutavad G servi
• 
  Servade fikseerimine graafis E(G)
• 
  Servagraaf E(G)

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

Üheksa väikseimat 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 klikikogum, kus G iga tipp kuulub täpselt kahte klikki.

Kirjandus

• Dharwadker, A., Pirzada, S. (2011) Graph Theory – Proc. Institute of Mathematics, Amazon Books, ISBN 1466254998.