Springen naar inhoud

Paden in graaf op n punten


  • Log in om te kunnen reageren

#1

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 14 september 2011 - 13:01

Hallo,

Mijn vraag is;
Hoeveel paden zijn er mogelijk als er n punten zijn?
Het gaat om een volledige graaf op n punten..
De paden moeten van 1 naar n lopen.

wat ik wel heb is
n=1 --> 0 paden --- graad 0, 0 lijnen
n=2 --> 2 paden --- graad 1, 1 lijn
n=3 --> 6 paden --- graad 2, 3 lijnen
n=4 --> 24 paden --- graad 3, 6 lijnen

Maar hoe moet ik nu verder?
ik zoek dus een formule om het aantal paden te vinden....

Alvast bedankt!

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

#2

In physics I trust

    In physics I trust


  • >5k berichten
  • 7384 berichten
  • Moderator

Geplaatst op 14 september 2011 - 13:20

Ik ben niet zeker, want grafentheorie is niet mijn specialiteit, maar wat ik wel opmerk:

n faculteit (n!) paden, LaTeX lijnen.
"C++ : Where friends have access to your private members." — Gavin Russell Baker.

#3

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 14 september 2011 - 13:41

De paden moeten van 1 naar n lopen.

...

n=2 --> 2 paden --- graad 1, 1 lijn

1 pad loopt van 1 naar 2. Wat is het andere pad?

#4

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 14 september 2011 - 13:49

1 pad loopt van 1 naar 2. Wat is het andere pad?


van 2 naar 1?
of geldt dat niet omdat je de puntnummering om kan draaien?

#5

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 14 september 2011 - 13:52

van 2 naar 1?

Maar jij zei:

De paden moeten van 1 naar n lopen.


#6

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 14 september 2011 - 13:57

Maar jij zei:


Klopt...
Dus;
n=2 heeft dan 1 pad (1,2)
n=3 heeft dan 2 paden (1,2,3 - 1,3)
n=4 heeft dan 5 paden (1,2,3,4 - 1,3,2,4 - 1,2,4 - 1,3,4 - 1,4)
?

Veranderd door Jaimy11, 14 september 2011 - 13:58


#7

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 15 september 2011 - 12:00

Klopt...
Dus;
n=2 heeft dan 1 pad (1,2)
n=3 heeft dan 2 paden (1,2,3 - 1,3)
n=4 heeft dan 5 paden (1,2,3,4 - 1,3,2,4 - 1,2,4 - 1,3,4 - 1,4)
?


Iemand uit mijn klas heeft het geprobeerd uit te leggen maar ik snap het nog steeds niet;
hij zegt dat je er een recursieformule van moet maken nl:

A(n-1)*(n-1)(n-2)+1? A(n-1) = antwoord van vorige n.
Heb ik mijn paden gewoon verkeerd of zit mijn klasgenoot ernaast, en hoe moet ik dit dan wel aanpakken?

Veranderd door Jaimy11, 15 september 2011 - 12:01


#8

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 15 september 2011 - 12:20

Stel dat A(n) een functie is die de waarde heeft van het aantal paden dat er van 1 naar n loopt. Merk op dat deze functie ook het aantal paden weergeeft van een willekeurig punt naar een willekeurig ander punt. Je kan immers altijd de punten hernummeren en hernummeren heeft geen enkele invloed op het aantal paden.

Stel nu dat je begint met van punt 1 naar punt 2 te gaan. Hoeveel paden lopen er van punt 2 naar n? Je weet dat punt 1 niet meer bezocht mag worden (daar ben je al geweest). Je kan nu alle punten hernummeren door 1 van het nummer af te trekken (dus 2 wordt 1, 3 wordt 2, enz., n wordt (n-1)). De vraag is dus gelijk aan: "Hoeveel paden lopen er van 1 naar (n-1)? Ofwel wat is de waarde van A(n-1).

Stel dat je nu begint met van punt 1 naar punt 3. De redenatie blijft hetzelfde, dus het aantal paden is hier wederom A(n-1). Zo kan je blijven beginnen met steeds een ander punt totdat je alle punten hebt gehad (punt 1 en punt n zijn geen valide keuzes). Je doet dit dus (n-2) keer.

Als je begint met van punt 1 naar punt n te gaan dan ben je meteen klaar. Dit is dus 1 pad.

Ik denk dat je nu een formule zou moeten kunnen opstellen:
LaTeX

Controleer je formule met de eerste paar antwoorden die je al weet...

#9

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 15 september 2011 - 12:31

Ik denk dat je nu een formule zou moeten kunnen opstellen:
LaTeX



Controleer je formule met de eerste paar antwoorden die je al weet...


Dus dan krijg je A(n) = (n-1)(n-2) - A(n-1) + 1.
Ok, deze klopt volgens mij ;)

#10

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 15 september 2011 - 12:40

Dus dan krijg je A(n) = (n-1)(n-2) - A(n-1) + 1.

Ik zie niet hoe je dat dan krijgt. Hoe kom je daarbij?

P.S. Anders gezegd: bereken A(5) eens volgens deze formule en tel hem eens uit met de hand. De antwoorden zijn niet hetzelfde.

Veranderd door EvilBro, 15 september 2011 - 12:46


#11

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 15 september 2011 - 13:20

Ik zie niet hoe je dat dan krijgt. Hoe kom je daarbij?

P.S. Anders gezegd: bereken A(5) eens volgens deze formule en tel hem eens uit met de hand. De antwoorden zijn niet hetzelfde.


Dat leek mij logisch, maar klopt inderdaad niet meer bij n=5....
En ik heb gekeken voor een andere recursie formule maar ben er tot nog toe niet opgekomen........
Heb al gekeken naar faculteiten en andere vormen maar er was niks nuttigs bij....

#12

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 15 september 2011 - 13:26

Dat leek mij logisch, maar klopt inderdaad niet meer bij n=5....
En ik heb gekeken voor een andere recursie formule maar ben er tot nog toe niet opgekomen........
Heb al gekeken naar faculteiten en andere vormen maar er was niks nuttigs bij....


Was nog even aan het kijken en kwam toen toch nog op dit antwoord:
A(n) = A(n-1)*(n-2)+1

maar het was meer uitproberen dan er een logisch geheel van maken, dus ik lees je verhaaltje hierboven nog even goed door en dan zou ik er wel uit moeten komen!

#13

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 15 september 2011 - 13:47

[quote name='Jaimy11' post='689202' date='15 September 2011, 14:20']Heb al gekeken naar faculteiten en andere vormen maar er was niks nuttigs bij....[/quote]
Een pad van 1 naar n bezit het punt 1, dan 0 of meer punten en uiteindelijk het punt n. Stel dat je alle paden van lengte 4 wilt weten. Dan moet je dus uit (n-2) punten twee punten kiezen. Dit kan op Bericht bekijken
Was nog even aan het kijken en kwam toen toch nog op dit antwoord:
A(n) = A(n-1)*(n-2)+1[/quote]
Dat is de juiste formule.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures