WisFaq!

Lijngrafen

We hebben een normale graaf G met n knooppunten en m takken. Nu moet ik het aantal takken berekenen van de lijngraaf L(G) in termen van de graden van de knooppunten van G. Maar hoe druk ik de graad van een knooppunt uit L(G) uit in termen van de graden van de knooppunten van G? Want als dat bekend is, hoef ik alleen nog maar door 2 te delen, omdat de takken dubbel worden geteld.
Alvast bedankt!

Veerle
18-9-2008

Antwoord

 
A    B    C 
 
 
F    E    D 

Noem G1 de graaf met knooppunten A,B,C,D,E en F en takken BC,CD,DE,EF,FA,BE en AB.
Noem G2 de graaf met knooppunten A,B,C,D,E en F en takken BC,CD,DE,EF,FA,BE en BD.

Beide grafen hebben evenveel knooppunten en evenveel takken. Wat is het aantal takken van de lijngraaf van G1? Wat is het aantal takken van de lijngraaf van G2?

cl
19-9-2008