Grafentheorie

Jaimy11

Hallo,

Ik zit met 3 vragen....

Ik zal beginnen met de naar mijn idee makkelijkste opgave;

1) Hoeveel bomen zijn er mogelijk in een graaf v={1,2,3,4,5}?

- Ik weet niet of volgorde belangrijk is (waarschijnlijk wel)

- Ik weet niet of ik 1,2 ook als boom moet zien, of echt alleen de mogelijk combinaties met 1 tm 5.

Ik weet wel dat je een boom op 5 punten op 3 verschillende manieren kan tekenen

1-2-3-4-5,

1-2-3-4, 5 onder/boven de 3

1-2-3-4-5 in de vorm van de 5 op een dobbelsteen of de vorm van een plus-teken als je hem kantelt.

2) Bewijs dat een bos (a punten, b componenten) a-b lijnen heeft

3) G is een Eulergraaf met een even aantal lijnen. a1,a2,...,an zijn de graden van de punten. Bewijs dat een deelgraaf dan graden (a1,a2,...,an)/2 heeft.

Bij 2 en 3 heb ik geen idee eigenlijk.................

Jaimy11

Jaimy11 schreef:Hallo,

Ik zit met 3 vragen....

Ik zal beginnen met de naar mijn idee makkelijkste opgave;

1) Hoeveel bomen zijn er mogelijk in een graaf v={1,2,3,4,5}?

- Ik weet niet of volgorde belangrijk is (waarschijnlijk wel)

- Ik weet niet of ik 1,2 ook als boom moet zien, of echt alleen de mogelijk combinaties met 1 tm 5.

Ik weet wel dat je een boom op 5 punten op 3 verschillende manieren kan tekenen

1-2-3-4-5,

1-2-3-4, 5 onder/boven de 3

1-2-3-4-5 in de vorm van de 5 op een dobbelsteen of de vorm van een plus-teken als je hem kantelt.

Klopt het dan dat het aantal bomen:

Voor 1,2,3,4,5: 5!

Voor 1,2,3,4-5 onder/boven 3: 4!

Voor 1,2,3,4,5 in de vorm van de 5: 3!*2!

=192 bomen?

Jaimy11

Jaimy11 schreef:Klopt het dan dat het aantal bomen:

Voor 1,2,3,4,5: 5!

Voor 1,2,3,4-5 onder/boven 3: 4!

Voor 1,2,3,4,5 in de vorm van de 5: 3!*2!

=192 bomen?

Ok, dat klopt niet,

En ik ga voor het antwoord wat ik gewoon logisch vond:

1) 5!/2

2) (5boven2)*3!

3) 5

Dus 125 manieren.

Verder ben ik gisteravond laat nog uit de 3e gekomen dus ik heb alleen voor vraag 2 nog geen oplossing kunnen bedenken:(

Iemand?

EvilBro

2) Bewijs dat een bos (a punten, b componenten) a-b lijnen heeft

Hoeveel lijnen zitten er in een boom met a punten? Hoeveel lijnen moet je hieruit verwijderen om van die ene boom, twee bomen (een bos) te maken?

Jaimy11

Hoeveel lijnen zitten er in een boom met a punten? Hoeveel lijnen moet je hieruit verwijderen om van die ene boom, twee bomen (een bos) te maken?

in een boom met 4 punten zitten 3 lijnen, in een boom met 5 punten zitten 4 lijnen, dus a-1 lijnen

om er een bos van te maken moet je 1 lijn verwijderen en dus a-2 lijnen nodig.......

Maar ik begrijp niet zo goed wat ze bedoelen met een component...

EvilBro

Maar ik begrijp niet zo goed wat ze bedoelen met een component...

elke boom is een component. In het voorbeeld begin je dus met 1 component (de boom). Door het verwijderen van 1 lijn, krijg je 2 componenten. enz.

Jaimy11

elke boom is een component. In het voorbeeld begin je dus met 1 component (de boom). Door het verwijderen van 1 lijn, krijg je 2 componenten. enz.

Dus als je a punten hebt en b componenten volgt hieruit, dat je b componenten uit de boom kan halen.

omdat je weet dat je maar 1 lijn weg hoeft te halen om een component te krijgen heb je maar 1 lijn minder nodig dan in je originele boom.

1 lijn minder betekent 1 component meer.

Dus het aantal lijnen is gelijk aan a-het aantal weggehaalde lijnen=a-aantal componenten=a-b?

Edit:

Foutieve laatste zin,

aantal lijnen in een bos is a-2 zoals in ander bericht beschreven

aantal lijnen = a-2 = a-aantal componenten (want 1 lijn verwijderen levert 2 componenten)

Wetenschapsforum

Laatste berichten

Nieuwsberichten

Grafentheorie

Grafentheorie

Re: Grafentheorie

Re: Grafentheorie

Re: Grafentheorie

Re: Grafentheorie

Re: Grafentheorie

Re: Grafentheorie