Grafentheorie
Moderators: ArcherBarry, Fuzzwood
- Berichten: 614
Grafentheorie
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.................
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.................
- Berichten: 614
Re: Grafentheorie
Klopt het dan dat het aantal bomen: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.
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?
- Berichten: 614
Re: Grafentheorie
Ok, dat klopt niet,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?
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?
-
- Berichten: 7.068
Re: Grafentheorie
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?2) Bewijs dat een bos (a punten, b componenten) a-b lijnen heeft
- Berichten: 614
Re: Grafentheorie
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...
-
- Berichten: 7.068
Re: Grafentheorie
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.Maar ik begrijp niet zo goed wat ze bedoelen met een component...
- Berichten: 614
Re: Grafentheorie
Dus als je a punten hebt en b componenten volgt hieruit, dat je b componenten uit de boom kan halen.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.
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)