Paden in graaf op n punten

Moderators: ArcherBarry, Fuzzwood

Reageer
Gebruikersavatar
Berichten: 614

Paden in graaf op n punten

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!

Gebruikersavatar
Berichten: 7.390

Re: Paden in graaf op n punten

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

n faculteit (n!) paden,
\(\frac{n \times (n-1)}{2}\)
lijnen.
"C++ : Where friends have access to your private members." Gavin Russell Baker.

Berichten: 7.068

Re: Paden in graaf op n punten

Jaimy11 schreef: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?

Gebruikersavatar
Berichten: 614

Re: Paden in graaf op n punten

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?

Berichten: 7.068

Re: Paden in graaf op n punten

van 2 naar 1?
Maar jij zei:
De paden moeten van 1 naar n lopen.

Gebruikersavatar
Berichten: 614

Re: Paden in graaf op n punten

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)

?

Gebruikersavatar
Berichten: 614

Re: Paden in graaf op n punten

Jaimy11 schreef: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?

Berichten: 7.068

Re: Paden in graaf op n punten

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:
\(A(n) = \cdots\)
Controleer je formule met de eerste paar antwoorden die je al weet...

Gebruikersavatar
Berichten: 614

Re: Paden in graaf op n punten

EvilBro schreef:Ik denk dat je nu een formule zou moeten kunnen opstellen:
\(A(n) = \cdots\)


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 ;)

Berichten: 7.068

Re: Paden in graaf op n punten

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.

Gebruikersavatar
Berichten: 614

Re: Paden in graaf op n punten

EvilBro schreef: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....

Gebruikersavatar
Berichten: 614

Re: Paden in graaf op n punten

Jaimy11 schreef: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!

Berichten: 7.068

Re: Paden in graaf op n punten

Heb al gekeken naar faculteiten en andere vormen maar er was niks nuttigs bij....
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
\({n-2 \choose 2}\)
Was nog even aan het kijken en kwam toen toch nog op dit antwoord:

A(n) = A(n-1)*(n-2)+1
Dat is de juiste formule.

Reageer