WisFaq!

Een formule om de punten of lijnen in een graaf te berekenen

Is er een formule waarmee je kan berekenen hoeveel punten of verbindingslijnen een graaf heeft? Bijv. als je het aantal punten weet dat je dan met een formule het aantal lijnen kan berekenen.

Hanneke
15-12-2005

Antwoord

Neem eens een graaf met drie punten. Weet je dan hoeveel lijntjes die graaf heeft? Je zou zeggen 3, maar mogen het er ook 2, 1 of 0 zijn?
Je kunt dus als je het aantal punten weet alleen het grootste (maximale) aantal lijntjes berekenen. (Of mogen er misschien tussen twee punten ook twee lijnen worden getekend?)
Als we nu even afspreken: we hebben een graaf van n punten en trekken tussen alle punten precies 1 lijn. Kunnen we dan ook uitrekenen hoeveel lijnen er zijn?
Ja, dat kan:
Vanuit elk punt kun je een lijn tekenen naar elk van de (n-1) overige punten.
Je krijgt dan n(n-1) lijntjes.
Maar ho eens even: we hebben dan elk lijntje precies 2 keer getekend: we moeten dus nog even delen door 2.
Tada: de formule wordt dan dus: ¹/₂n(n-1)

hk
17-12-2005