Springen naar inhoud

Grafentheorie


  • Log in om te kunnen reageren

#1

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 21 september 2011 - 20:15

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.................

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

#2

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 22 september 2011 - 09:56

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?

#3

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 22 september 2011 - 11:04

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?

#4

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 22 september 2011 - 12:24

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?

#5

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 22 september 2011 - 12:38

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...

#6

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 22 september 2011 - 12:40

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.

#7

Jaimy11

    Jaimy11


  • >250 berichten
  • 614 berichten
  • Ervaren gebruiker

Geplaatst op 22 september 2011 - 12:45

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)

Veranderd door Jaimy11, 22 september 2011 - 12:50






0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures