Springen naar inhoud

Grafentheorie


  • Log in om te kunnen reageren

#1

Dijkstra

    Dijkstra


  • 0 - 25 berichten
  • 10 berichten
  • Gebruiker

Geplaatst op 16 januari 2009 - 19:31

Gegeven een boom met p punten.
Hoeveel lijnen moet men toevoegen om er een maximaal vlakke graaf van te maken?

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

kee

    kee


  • >250 berichten
  • 389 berichten
  • Ervaren gebruiker

Geplaatst op 22 januari 2009 - 16:57

Intussen lijkt het antwoord via google te vinden te zijn. Ben jij soms dezelfde?

Ik citeer van google:

Als q het aantal lijnen en f het aantal facetten is, dan moet 3f=2q om een maximaal vlakke graaf te hebben (want elke lijn grenst aan 2 facetten en elk facet wordt door 3 lijnen omgeven). Omdat p-q+f=2 moet (vorige vergelijking invullen en uitwerken) q=3p-6. Elke boom van p punten heeft p-1 lijnen, dus (3p - 6) - (p - 1) = 2p - 5 lijnen om erbij te tekenen. Neem b.v. 3 punten: 6 - 5 = 1. neem 4 punten: 8 - 5 = 3. Neem 5 punten: 10 - 5 = 5.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures