SES School, Studie en Onderwijs
Wiskunde in de brugklas, Frans voor het examen of een studie Personeel en Arbeid? Moeilijke formulieren van DUO? Iets weten over studiefinanciering of studentenverenigingen? Dit is het forum voor leerkrachten, scholieren en studenten, van brugklas tot uni
Nee, ook niet 5… we hebben de berekening voor het aantal labellings van een pad van 5 toch al eens gedaan?quote:Op donderdag 20 november 2008 23:39 schreef Borizzz het volgende:
Ok, dus maar 5 mogelijkheden als we naar 1 spaak kijken.
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Ik heb er nu dit van gemaakt:
B C
A
E D
Als k=1 dan is er 1 spaak die wordt meegenomen. Een opspannende boom heeft dan 60 mogelijkheden. Het was immers een gelabelde graaf en dus maakt het uit welk punt in het centrum is.
Als k=2 worden er 2 spaken in de opspannende boom meegenomen. Ook dit levert een pad op met wederom 60 mogelijke opspannende bomen.
Als k=3 dan worden er 3 spaken meegenomen in de opspannende boom. 0 mogelijkheden omdat ik dan een cykel krijg.
Als k=4 dan worden er 4 spaken meegenomen. De opspannende boom bestaat dan alleen uit spaken. 5 mogelijkheden omdat het uitmaakt welk punt in het centrum zit.
Samen dus 60+60+0+5 = 125 mogelijke opspannende bomen.
B C
A
E D
Als k=1 dan is er 1 spaak die wordt meegenomen. Een opspannende boom heeft dan 60 mogelijkheden. Het was immers een gelabelde graaf en dus maakt het uit welk punt in het centrum is.
Als k=2 worden er 2 spaken in de opspannende boom meegenomen. Ook dit levert een pad op met wederom 60 mogelijke opspannende bomen.
Als k=3 dan worden er 3 spaken meegenomen in de opspannende boom. 0 mogelijkheden omdat ik dan een cykel krijg.
Als k=4 dan worden er 4 spaken meegenomen. De opspannende boom bestaat dan alleen uit spaken. 5 mogelijkheden omdat het uitmaakt welk punt in het centrum zit.
Samen dus 60+60+0+5 = 125 mogelijke opspannende bomen.
kloep kloep
Nee. Kijk eerst wat voor vorm de boom heeft? Is het b.v. een pad? Of is het wat anders? Of een ster? Of wat? Kijk dán op hoeveel manieren een pad te labellen is.
Bijvoorbeeld met 1 spaak kun je een pad krijgen, en je kunt iets krijgen als:
Bij twee spaken kun je óók een pad krijgen (dus dat haalt niets uit). Je kunt ook bovenstaande weer krijgen. Maakt dus ook niet uit. Met drie spaken kun je géén pad krijgen. Wel bovenstaande. Haalt dus niets uit. Bij vier spaken krijg je een ster.
Dat zijn de drie basisvormen. Dan ga je kijken hoe je die kunt labellen.
Bijvoorbeeld met 1 spaak kun je een pad krijgen, en je kunt iets krijgen als:
| 1 2 3 | | o-o-o-o |
Bij twee spaken kun je óók een pad krijgen (dus dat haalt niets uit). Je kunt ook bovenstaande weer krijgen. Maakt dus ook niet uit. Met drie spaken kun je géén pad krijgen. Wel bovenstaande. Haalt dus niets uit. Bij vier spaken krijg je een ster.
Dat zijn de drie basisvormen. Dan ga je kijken hoe je die kunt labellen.
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Maar dan is het met 1 spaak mogelijk:
- pad (60 mogelijkheden)
- reeks van 4 met en 1 punt met graad 2. Dit heeft dan 60 mogelijkheden?
- pad (60 mogelijkheden)
- reeks van 4 met en 1 punt met graad 2. Dit heeft dan 60 mogelijkheden?
kloep kloep
Ja. En dan die ster nog, en we zijn er.quote:
Maar dan is het met 1 spaak mogelijk:
- pad (60 mogelijkheden)
- reeks van 4 met en 1 punt met graad 2. Dit heeft dan 60 mogelijkheden?
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Even samenvatten:
Ik ga uit van een wielgraaf met A in het midden en B,C,D, E op de hoeken.
B C
A
E D
Als k=1 dan is er 1 spaak die wordt meegenomen.
Een mogelijke opspannende boom is dan en pad. Een labeling van het pad is dan A-B-C-D-E. Het aantal mogelijkheden voor een opspannende boom is dan 60. mogelijkheden. Het was immers een gelabelde graaf en dus maakt het uit welk punt in het centrum is.
Ook is een volgende opspannende boom mogelijk
A-B-D-E
|
C
Dit type heeft 60 mogelijke opspannende bomen. Samen 120 opspannende bomen.
Als k=2 worden er 2 spaken in de opspannende boom meegenomen.
Ook dit levert een pad op met wederom 60 mogelijke opspannende bomen. Ook het andere type als onder k=1 is te krijgen, met 60 mogelijkheden.
Samen 120 opspannende bomen
Als k=3 dan worden er 3 spaken meegenomen in de opspannende boom. 60 mogelijkheden omdat alleen het type A-B-D-E voorkomt.
|
C
Als k=4 dan worden er 4 spaken meegenomen. De opspannende boom bestaat dan alleen uit spaken. 5 mogelijkheden omdat het uitmaakt welk punt in het centrum zit.
Samen dus 120+120+60+5 = 305 mogelijke opspannende bomen voor wielgraaf W4.
??? Maar k heb het gevoel dat ik nu weer alles dubbeltel.
Ik ga uit van een wielgraaf met A in het midden en B,C,D, E op de hoeken.
B C
A
E D
Als k=1 dan is er 1 spaak die wordt meegenomen.
Een mogelijke opspannende boom is dan en pad. Een labeling van het pad is dan A-B-C-D-E. Het aantal mogelijkheden voor een opspannende boom is dan 60. mogelijkheden. Het was immers een gelabelde graaf en dus maakt het uit welk punt in het centrum is.
Ook is een volgende opspannende boom mogelijk
A-B-D-E
|
C
Dit type heeft 60 mogelijke opspannende bomen. Samen 120 opspannende bomen.
Als k=2 worden er 2 spaken in de opspannende boom meegenomen.
Ook dit levert een pad op met wederom 60 mogelijke opspannende bomen. Ook het andere type als onder k=1 is te krijgen, met 60 mogelijkheden.
Samen 120 opspannende bomen
Als k=3 dan worden er 3 spaken meegenomen in de opspannende boom. 60 mogelijkheden omdat alleen het type A-B-D-E voorkomt.
|
C
Als k=4 dan worden er 4 spaken meegenomen. De opspannende boom bestaat dan alleen uit spaken. 5 mogelijkheden omdat het uitmaakt welk punt in het centrum zit.
Samen dus 120+120+60+5 = 305 mogelijke opspannende bomen voor wielgraaf W4.
??? Maar k heb het gevoel dat ik nu weer alles dubbeltel.
kloep kloep
Nee. Die padgraaf voor k = 2 en k = 1 maakt geen verschil. Het gaat om de vorm van de opspannende boom. Aan de boom kun je niet meer ruiken welke lijn een spaak was en welke niet. (Althans, zo zou ik dat interpreteren.)
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Dus mijn afsluitende verhaal klopt wel?
Ik merk dat ik echt nog wat goed te maken heb met mogelijkheden uittellen. Wat telproblematiek dus.
Weet jij daar een cursus oid voor? T zit me namelijk niet zo lekker dat ik dat moeilijk blijf vinden.
Ik merk dat ik echt nog wat goed te maken heb met mogelijkheden uittellen. Wat telproblematiek dus.
Weet jij daar een cursus oid voor? T zit me namelijk niet zo lekker dat ik dat moeilijk blijf vinden.
kloep kloep
Nee, je komt gewoon op 125 uit. 60 + 60 + 5. Je hebt voor k = 1 al gevonden dat de opspannende boom een padgraaf kan zijn, die padgrafen van k = 2 maken dan niets meer uit, die moet je niet nog een keer meetellen. Een padgraaf blijft een padgraaf…quote:
Dus mijn afsluitende verhaal klopt wel?
Ik merk dat ik echt nog wat goed te maken heb met mogelijkheden uittellen. Wat telproblematiek dus.
Weet jij daar een cursus oid voor? T zit me namelijk niet zo lekker dat ik dat moeilijk blijf vinden.
Ik zou naar je universiteitsbibliotheek gaan en een boek over combinatoriek uit de kast vissen, of je docent vragen welk boek hij gebruikt/aanraadt. Zelf heb ik met Discrete Mathematics van Biggs gewerkt.
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Heey, ik heb nu mijn Wiskunde A-lympiade 21 nov. 2008 Voorronde opdracht voor me. Het heet Evacuatie. Meer mensen die er nu mee bezig zijn? Want ik snap opdracht 4 niet en de opdracht is te lang om het hier te typen... Mensen die me hierbij kunnen helpen?
.
Is het niet de bedoeling dat je dit zonder hulp van anderen doet?quote:
Heey, ik heb nu mijn Wiskunde A-lympiade 21 nov. 2008 Voorronde opdracht voor me. Het heet Evacuatie. Meer mensen die er nu mee bezig zijn? Want ik snap opdracht 4 niet en de opdracht is te lang om het hier te typen... Mensen die me hierbij kunnen helpen?
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Hij doet de ParA-lympiade voor mensen met een wiskundige handicap.quote:Op vrijdag 21 november 2008 10:38 schreef Iblis het volgende:
[..]
Is het niet de bedoeling dat je dit zonder hulp van anderen doet?
Ja precies... nog sociale(re) mensen die kunnen helpen? het gaat me hier echt om mijn P.O. cijfer en niet om zown wedstrijd waar ik toch niet aan mee wil doen. [ben nooit goed geweest in Wiskunde]
Ikl vraag hier niet om de antwoorden maar om uitleg!
Ikl vraag hier niet om de antwoorden maar om uitleg!
.
Ik denk dat de mensen die je kunnen antwoorden voorlopig nog bezig zijn met de voorronde van de Wiskunde A-lympiade. Als je toch anderen kunt vragen, is het dan niet het handigst om je docent te vragen?quote:Op vrijdag 21 november 2008 10:46 schreef Rainb0ws het volgende:
Ja precies... nog sociale(re) mensen die kunnen helpen? het gaat me hier echt om mijn P.O. cijfer en niet om zown wedstrijd waar ik toch niet aan mee wil doen. [ben nooit goed geweest in Wiskunde]
Ikl vraag hier niet om de antwoorden maar om uitleg!
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Het is niet de bedoeling dat je vandaag al inhoudelijke berichten plaatst over de A-lympiade omdat die wedstrijd nu loopt en het gewoon oneerlijk is voor de mensen die daaraan meedoen.
eee7a201261dfdad9fdfe74277d27e68890cf0a220f41425870f2ca26e0521b0
Nieuw grafentheoretisch probleem.
Het gaat om een volledige tweedelingsgraaf K2,4.
Deze graaf bestaat uit twee punten a en vier punten b.
Een paar van de vragen erover.
1) Hoeveel opspannende bomen zijn er als de graad van 1 punt van a gelijk is aan 1.
Ik denk dan dat het andere punt van a de graden 1 t/m 4 moet kunnen hebben. Vier punten b hebben graad 1, of 3 punten b hebben graad 1 en eentje graad 2. Dit zijn de mogelijke opties. Maar hoe kan ik nu door handig tellen het aantal opspannende bomen vinden?
2)
Toon aan dat K2,4 12 opspannende bomen heeft als de graad van één punt van a gelijk is aan 2. Ik heb er veel uitgetekend en ook hier geldt weer dat dit het antwoord onder 1) is + het aantal opspannende bomen als beide punten a graad 2 hebben, een punt a graad 3 en een punt a graad 4. Maar weer: het handig tellen lukt me niet.
3)
Dit moet door 1) en 2) te combineren het totaal aantal opspannene bomen opleveren voor K2,4. Kan dit gewoon door een optelling van de antwoorden bij 1) en 2)? Of moet dan graad 3 en 4 erbij komen?
4)
Sommatieformule vinden voor het aantal opspannende bomen van K2,x. Dus nu in het algemeen... Maar aangezien ik 1) en 2) nog niet vinden kan lukt dit nog niet.
Het gaat om een volledige tweedelingsgraaf K2,4.
Deze graaf bestaat uit twee punten a en vier punten b.
Een paar van de vragen erover.
1) Hoeveel opspannende bomen zijn er als de graad van 1 punt van a gelijk is aan 1.
Ik denk dan dat het andere punt van a de graden 1 t/m 4 moet kunnen hebben. Vier punten b hebben graad 1, of 3 punten b hebben graad 1 en eentje graad 2. Dit zijn de mogelijke opties. Maar hoe kan ik nu door handig tellen het aantal opspannende bomen vinden?
2)
Toon aan dat K2,4 12 opspannende bomen heeft als de graad van één punt van a gelijk is aan 2. Ik heb er veel uitgetekend en ook hier geldt weer dat dit het antwoord onder 1) is + het aantal opspannende bomen als beide punten a graad 2 hebben, een punt a graad 3 en een punt a graad 4. Maar weer: het handig tellen lukt me niet.
3)
Dit moet door 1) en 2) te combineren het totaal aantal opspannene bomen opleveren voor K2,4. Kan dit gewoon door een optelling van de antwoorden bij 1) en 2)? Of moet dan graad 3 en 4 erbij komen?
4)
Sommatieformule vinden voor het aantal opspannende bomen van K2,x. Dus nu in het algemeen... Maar aangezien ik 1) en 2) nog niet vinden kan lukt dit nog niet.
kloep kloep
Ik zie nog niet helemaal wat je doet. Als je je punten aan de ene kant beide a noemt, en aan de andere kant allevier 'b', dan creëer je heel veel symmetrie en is het aantal opspannende bomen volgens mij heel veel lager dan jij denkt.
Je weet dat een boom op 6 punten 5 lijnen moet hebben. Heb je dus één van je punten a graad 1 gegeven, dan moeten de overige vier lijnen op het andere punt a uitkomen. Er is dan één b-punt dat graad 2 heeft. Welk b-punt dat is bepaalt het aantal mogelijkheden (samen met welk a-punt graad 1 heeft, en welke graad 4).
Voor onderdeel 2 geldt een soortgelijke constatering: als één punt graad 2 heeft, heeft het andere punt graad 3. En er is wederom 1 b-punt met graad 2. Jij stelt daar ook een situatie waarin punt a graad 4 heeft – maar daar kan ik me niets bij voorstellen. Als je een punt a met graad 2 en een punt a met graad 4 hebt, dan heb je sowieso zes lijnen in je graaf, en dat moet een cykel geven op 6 punten.
Je weet dat een boom op 6 punten 5 lijnen moet hebben. Heb je dus één van je punten a graad 1 gegeven, dan moeten de overige vier lijnen op het andere punt a uitkomen. Er is dan één b-punt dat graad 2 heeft. Welk b-punt dat is bepaalt het aantal mogelijkheden (samen met welk a-punt graad 1 heeft, en welke graad 4).
Voor onderdeel 2 geldt een soortgelijke constatering: als één punt graad 2 heeft, heeft het andere punt graad 3. En er is wederom 1 b-punt met graad 2. Jij stelt daar ook een situatie waarin punt a graad 4 heeft – maar daar kan ik me niets bij voorstellen. Als je een punt a met graad 2 en een punt a met graad 4 hebt, dan heb je sowieso zes lijnen in je graaf, en dat moet een cykel geven op 6 punten.
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Eerst even onderdeel 1).
Ik heb de graaf ongeveer zo: a1 is het punt met graad 1, a2 is het andere punt.
a1 - b1 - a2
b2
b3
b4 (invoeren lukt niet helemaal, de b-punten moeten allemaal onder elkaar)
Boom bevat maximaal 5 lijnen, anders heb ik een cykel. Dus als a1 vast staat op graad 1, kom ik niet verder dan 4 mogelijkheden omdat b1, b2, b3 ,b4 allen een keer graad 2 kunnen hebben. Dit correct voor onderdeel 1?
Ik heb de graaf ongeveer zo: a1 is het punt met graad 1, a2 is het andere punt.
a1 - b1 - a2
b2
b3
b4 (invoeren lukt niet helemaal, de b-punten moeten allemaal onder elkaar)
Boom bevat maximaal 5 lijnen, anders heb ik een cykel. Dus als a1 vast staat op graad 1, kom ik niet verder dan 4 mogelijkheden omdat b1, b2, b3 ,b4 allen een keer graad 2 kunnen hebben. Dit correct voor onderdeel 1?
kloep kloep
Waarom zou je altijd het punt met graad 1 a1 noemen?
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Je wilt het aantal opspannende bomen berekenen. Als je dan stelt dat alleen punt a1 graad 1 mag hebben dan mis je alle situaties waarin punt a2 graad 1 heeft…quote:
Omdat ik de punten goed uit elkaar wil houden...
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Maar in deze opdracht moet a1 graad 1 hebben. Dus dan is het toch altijdzo dat a2 graad 4 heeft...
a1 zit vast aan graad 1. Of is het dan zo dat meer punten b graad 2 kunnen hebben?
Ik heb nu dit als idee:
Het aantal opspannende bomen van K2,4 met als voorwaarde (a1)=1.
Dit houdt in dat a1 maar verbonden mag zijn met één punt b. Verder heeft een boom die bestaat uit 6 punten 5 lijnen. Een van die lijnen gaat naar punt a1. Dus: de overige 4 lijnen gaan allen naar a2. A2 heeft dus graad 4. De punten b hebben dan graad 1 of graad 2. Het hangt er nu alleen nog van af welk punt b graad 2 heeft. Aangezien er 4 punten b zijn, zijn er dus ook 4 mogelijke opspannende bomen.
a1 zit vast aan graad 1. Of is het dan zo dat meer punten b graad 2 kunnen hebben?
Ik heb nu dit als idee:
Het aantal opspannende bomen van K2,4 met als voorwaarde (a1)=1.
Dit houdt in dat a1 maar verbonden mag zijn met één punt b. Verder heeft een boom die bestaat uit 6 punten 5 lijnen. Een van die lijnen gaat naar punt a1. Dus: de overige 4 lijnen gaan allen naar a2. A2 heeft dus graad 4. De punten b hebben dan graad 1 of graad 2. Het hangt er nu alleen nog van af welk punt b graad 2 heeft. Aangezien er 4 punten b zijn, zijn er dus ook 4 mogelijke opspannende bomen.
kloep kloep
Kijk, dit is één mogelijkheid:
Maar dit is er net zo goed een:
Zijn deze anders? Ja! Want in het ene geval heeft a1 graad 4, en in het andere geval heeft a2 graad 4.
| 1 2 3 4 5 6 7 | __/ / --b2 | / || --b3 ||/ a2---b4 |
Maar dit is er net zo goed een:
| 1 2 3 4 5 6 7 8 | ||\ || \-b2 | \ \ \-b3 \ \ a2---b4 |
Zijn deze anders? Ja! Want in het ene geval heeft a1 graad 4, en in het andere geval heeft a2 graad 4.
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Oké, dan was je onnauwkeuring in je probleemformulering. Want je zei eerst: Hoeveel opspannende bomen zijn er als de graad van 1 punt van a gelijk is aan 1. En 1 punt van a zou ik zeggen is óf a1 óf a2… Maar als het alleen a1 is, dan klopt het inderdaad wat je zegt.quote:
Maar in deze opdracht moet a1 graad 1 hebben. Dus dan is het toch altijdzo dat a2 graad 4 heeft...
a1 zit vast aan graad 1. Of is het dan zo dat meer punten b graad 2 kunnen hebben?
Ik heb nu dit als idee:
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
De opdracht die ik moet maken is opbouwend bedoeld.
Ik zal proberen wat nauwkeuriger te zijn.
Dus we zijn het eens dat als a1 graad 1 heeft (en dat staat vast) dat het aantal opspannende bomen dus 4 is.
nu de vervolg vraag:
2) Nu is gegeven dat a1 graad 2 heeft en ook dat is een vast gegeven. Gevraagd is weer (voor de afwisseling!) het aantal opspannende bomen:
Ik heb dan dit als antwoord:
Ook hier geldt weer dan de boom bestaat uit 5 lijnen. Als a1 graad 2 heeft, betekent dit dat a2 graad 3 heeft (als de graad van a2 lager is dan is het geen samenhangende graaf meer, en als de graad hoger is heb ik teveel lijnen en een cykel in de boom). Er mag net als in 1) maar één punt b zijn met graad 2, de rest van de punten b hebben graad 1.
Het gaat er nu om uit te rekenen op hoeveel manieren a1 met de 4 punten b kan worden verbonden en hetzelfde voor punt a2. Dus 4!/(2!*1!*1!) 4 boven 2 is 12 mogelijke opspannende bomen.
Je ziet dat ik probeer uitgebreid een antwoord te geven. Aangezien ik ervan wil leren. Ook over dit onderdeel zal weer (over een paar maanden een tentamen volgen, en dus wil ik de onderste steen boven.)
Ik zal proberen wat nauwkeuriger te zijn.
Dus we zijn het eens dat als a1 graad 1 heeft (en dat staat vast) dat het aantal opspannende bomen dus 4 is.
nu de vervolg vraag:
2) Nu is gegeven dat a1 graad 2 heeft en ook dat is een vast gegeven. Gevraagd is weer (voor de afwisseling!) het aantal opspannende bomen:
Ik heb dan dit als antwoord:
Ook hier geldt weer dan de boom bestaat uit 5 lijnen. Als a1 graad 2 heeft, betekent dit dat a2 graad 3 heeft (als de graad van a2 lager is dan is het geen samenhangende graaf meer, en als de graad hoger is heb ik teveel lijnen en een cykel in de boom). Er mag net als in 1) maar één punt b zijn met graad 2, de rest van de punten b hebben graad 1.
Het gaat er nu om uit te rekenen op hoeveel manieren a1 met de 4 punten b kan worden verbonden en hetzelfde voor punt a2. Dus 4!/(2!*1!*1!) 4 boven 2 is 12 mogelijke opspannende bomen.
Je ziet dat ik probeer uitgebreid een antwoord te geven. Aangezien ik ervan wil leren. Ook over dit onderdeel zal weer (over een paar maanden een tentamen volgen, en dus wil ik de onderste steen boven.)
kloep kloep
Ik snap dat de vraag opbouwend is, maar als je ze niet nauwkeurig formuleert hier dan zit ik een ander probleem op te lossen natuurlijk. Bij 2 is je redenatie correct. De berekening zelf vind ik echter wat warrig, ik zou zeggen: Het gaat er nu om uit te rekenen op hoeveel manieren a1 met de 2 van de 4 punten b kan worden verbonden. Dit geeft (4 boven 2) = 4!(2!2!) = 6 mogelijkheden (ik snap niet helemaal hoe jij aan je 1! 1! komt). Dat de andere twee niet-verbonden punten van b met a2 moeten worden verbonden is evident. Dan is echter voor de 5e lijn nog de keus met welke van de twee punten die ook met a1 verbonden zijn je deze verbindt. Dat geeft 2 mogelijkheden, dus totaal: 2 * (4 boven 2) = 12. (Je antwoordt klopt dus, maar ik volg je berekening niet geheel.)
Voor 3 geldt dat je niet simpelweg door optelling tot het antwoord komt, maar je bent vrij dichtbij.
Bij 2 is je redenatie correct. De berekening zelf vind ik echter wat warrig, ik zou zeggen: Het gaat er nu om uit te rekenen op hoeveel manieren a1 met de 2 van de 4 punten b kan worden verbonden. Dit geeft (4 boven 2) = 4!(2!2!) = 6 mogelijkheden (ik snap niet helemaal hoe jij aan je 1! 1! komt). Dat de andere twee niet-verbonden punten van b met a2 moeten worden verbonden is evident. Dan is echter voor de 5e lijn nog de keus met welke van de twee punten die ook met a1 verbonden zijn je deze verbindt. Dat geeft 2 mogelijkheden, dus totaal: 2 * (4 boven 2) = 12. (Je antwoordt klopt dus, maar ik volg je berekening niet geheel.)Voor 3 geldt dat je niet simpelweg door optelling tot het antwoord komt, maar je bent vrij dichtbij.
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Bij 2) dacht ik mbt de berekening aan 4 punten b. van die vier punten zijn er 2 equivalent (zo als je mij een paar dagen geleden leerde). en de twee andere zijn uniek. Dus: 4 boven 2.
Bij 3) is het de volgende vraag: bepaal nu door systematisch tellen het aantal opspannende bomen bij K2,4.
Mijn oplossing gaat dan als volgt:
De aantallen opspannende bomen die onder 1) en 2) zijn berekend zijn symmetrisch ware het niet dat het een gelabelde graaf is. Het totale aantal opspannende bomen uit 1) en 2) is dus 4+12=16. Vanwege symmetrie geldt dat voor een gelabelde graaf K2,4 geldt dat het belangrijk is welk punt waar staat. Dus 2*16= totaal 32 opspannende bomen voor een gelabelde graaf K2,4
Bij 3) is het de volgende vraag: bepaal nu door systematisch tellen het aantal opspannende bomen bij K2,4.
Mijn oplossing gaat dan als volgt:
De aantallen opspannende bomen die onder 1) en 2) zijn berekend zijn symmetrisch ware het niet dat het een gelabelde graaf is. Het totale aantal opspannende bomen uit 1) en 2) is dus 4+12=16. Vanwege symmetrie geldt dat voor een gelabelde graaf K2,4 geldt dat het belangrijk is welk punt waar staat. Dus 2*16= totaal 32 opspannende bomen voor een gelabelde graaf K2,4
kloep kloep
Ja, 32 in totaal. Nu is het tijd voor 4.
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Mooi zo. De berekening onder 2) snap ik ook. Zat even niet op te letten.
4) De sommatieformule voor het totaal aantal opspannende bomen van een gelabelde tweedelingsgraaf K2,x
Eerst een inventarisatie van wat ik al weet:
K2,1 heeft 1 opspannende boom
K2,2 heeft 4 opspannende bomen
K2,3 heeft 12 opspannende bomen
K2,4 heeft 32 opspannende bomen
Maar ik kan hier niet zomaar een regelmaat in vinden. Sommatie zegt mij dat ik bv de vorige moet optellen dus
(ik probeer maar wat)
voor K2,3 wordt dat 1+4 =5 , maar nu van de 5 naar 12 toe (*2 en dan +2)
voor K2,4 wordt dat 1+4+12=17 en van 17 naar 32 toe (*2 en dan -2)
maar dit zie ik nog niet.
4) De sommatieformule voor het totaal aantal opspannende bomen van een gelabelde tweedelingsgraaf K2,x
Eerst een inventarisatie van wat ik al weet:
K2,1 heeft 1 opspannende boom
K2,2 heeft 4 opspannende bomen
K2,3 heeft 12 opspannende bomen
K2,4 heeft 32 opspannende bomen
Maar ik kan hier niet zomaar een regelmaat in vinden. Sommatie zegt mij dat ik bv de vorige moet optellen dus
(ik probeer maar wat)
voor K2,3 wordt dat 1+4 =5 , maar nu van de 5 naar 12 toe (*2 en dan +2)
voor K2,4 wordt dat 1+4+12=17 en van 17 naar 32 toe (*2 en dan -2)
maar dit zie ik nog niet.
kloep kloep
Dit lijkt me niet helemaal de manier om het aan te pakken. Op zich kun je zo'n reeks invoeren in Sloane's encyclopedia of integer sequences, en dan vind je of het een bekende reeks is en welke formules ervoor zijn, etc. Maar afleiden is toch beter.
Men neme de graaf K2,x. Dan heb je de volgende mogelijkheden: Punt a1 heeft graad 1, heeft graad 2, heeft graad 3, heeft graad 4, heeft graad 5, etc. Als punt a1 graad p heeft, hoeveel mogelijkheden zijn er dan om p punten uit de x punten te kiezen? Op hoeveel verschillende manieren kunnen nu de overige lijnen nog neergelegd worden? Kun je zo'n uitdrukking vinden in termen van p en x?
Zo ja, sommeer dan over p. (Die formule kent een vereenvoudiging trouwens.)
Men neme de graaf K2,x. Dan heb je de volgende mogelijkheden: Punt a1 heeft graad 1, heeft graad 2, heeft graad 3, heeft graad 4, heeft graad 5, etc. Als punt a1 graad p heeft, hoeveel mogelijkheden zijn er dan om p punten uit de x punten te kiezen? Op hoeveel verschillende manieren kunnen nu de overige lijnen nog neergelegd worden? Kun je zo'n uitdrukking vinden in termen van p en x?
Zo ja, sommeer dan over p. (Die formule kent een vereenvoudiging trouwens.)
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Vreemd toch heb ik ooit geleerd om het op deze manier aan te pakken.
Maar goed. Afleiden.
K2,x. dus 2 punten a en x punten b.
a1 heeft graad p. dat wordt dan x! /(x-p)!*p! ?
Maar goed. Afleiden.
K2,x. dus 2 punten a en x punten b.
a1 heeft graad p. dat wordt dan x! /(x-p)!*p! ?
kloep kloep
Dat is een tamelijk lastige onderneming als je een uitdrukking hebt die gegeven wordt door iets moeilijkers dan een lineaire relatie.quote:
Vreemd toch heb ik ooit geleerd om het op deze manier aan te pakken.
[/quote]
Voor wat precies? En staan je haakjes goed?quote:a1 heeft graad p. dat wordt dan x! /(x-p)!*p! ?
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
x! / ( (x-p)! * p! )
dit zou zijn het aantal manieren waarop a1 met x punten b kan worden verbonden.
als dit klopt is er het omgekeerde voor a2, want a2 wordt verbonden met punten b die niet aan a1 vast zitten?
dit zou zijn het aantal manieren waarop a1 met x punten b kan worden verbonden.
als dit klopt is er het omgekeerde voor a2, want a2 wordt verbonden met punten b die niet aan a1 vast zitten?
kloep kloep
Niet het omgekeerde voor a2,van de (x - p) niet verbonden punten is duidelijk dat ze allemaal met a2 verbonden moeten worden. Daar is geen keus voor. Er blijft dan nog maar één lijnstuk over waarvoor wat te kiezen valt. Je keus voor a1 forceert dus op één lijn na een keus voor a2. (Zie m'n uitleg over K4,2)quote:
x! / ( (x-p)! * p! )
dit zou zijn het aantal manieren waarop a1 met x punten b kan worden verbonden.
als dit klopt is er het omgekeerde voor a2, want a2 wordt verbonden met punten b die niet aan a1 vast zitten?
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Ja, inderdaad; dat ene lijnstuk waar nog wat voor te kiezen valt maakt er juist een boom van. Daarvoor zijn x opties (er waren immers x punten b).
Dus dan kom ik op: x! / ( (x-p)! * p! ) * x als aantal opspannende bomen. Voor K2,x
Dus dan kom ik op: x! / ( (x-p)! * p! ) * x als aantal opspannende bomen. Voor K2,x
kloep kloep
Niet helemaal. a1 heeft graad p. Dus kun je a1 op (x boven p) = x!(p!(x-p)!) manieren verbinden met punten van b. Voor a2 ligt de keus op één lijn na dan vast. Maar die ene lijn moet verbonden worden met één van de punten die nu met a1 verbonden is (anders zou je een dubbele lijn krijgen en geen verbonden graaf): je hebt dus p mogelijkheden daarvoor. En dat geeft dat het aantal mogelijkheden waar bij punt a1 graad p heeft gelijk is aan:quote:
Ja, inderdaad; dat ene lijnstuk waar nog wat voor te kiezen valt maakt er juist een boom van. Daarvoor zijn x opties (er waren immers x punten b).
Dus dan kom ik op: x! / ( (x-p)! * p! ) * x als aantal opspannende bomen. Voor K2,x
[ Bericht % gewijzigd door motorbloempje op 01-09-2013 21:21:35 ]
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Dan krijg ik dus x! / ( (x-p)! * p! ) * p als aantal opspannende bomen.
Inderdaad p mogelijkheden... steeds blijven denken dat het een boom is.
Maar dit is nog geen sommatieformule toch?
Inderdaad p mogelijkheden... steeds blijven denken dat het een boom is.
Maar dit is nog geen sommatieformule toch?
kloep kloep
Nee, dat klopt. Maar je hebt nu een uitdrukking voor het geval dat a1 graad p heeft. Gaan we nu terug naar K4,2 dan zien we dat a1 of graad 1 kan hebben, of graad 2, of graad 3 of graad 4, als we dat invullen vinden we dus dat we moeten krijgen:quote:
Dan krijg ik dus x! / ( (x-p)! * p! ) * p als aantal opspannende bomen.
Inderdaad p mogelijkheden... steeds blijven denken dat het een boom is.
Maar dit is nog geen sommatieformule toch?
En dit is gelijk aan: 1*4 + 2*6 + 3*4 + 4*1 = 4 + 12 + 12 + 4 = 32.
In het algemene geval luidt de somformule dus…
[ Bericht % gewijzigd door motorbloempje op 01-09-2013 21:20:33 ]
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Ja, typefoutje, maar het is natuurlijk volkomen identiek.quote:
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Ja, dus:
En als we dan eens kijken voor x = 4: 4*23 = 32; voor x = 3: 3*22 = 12, voor x = 2: 2*2 = 4. Het klopt als een zwerende vinger met wat je gevonden hebt. Maar, dit verband was lastig te vinden geweest door alleen naar het rijtje te kijken (denk ik).
[ Bericht % gewijzigd door motorbloempje op 01-09-2013 21:21:40 ]
En als we dan eens kijken voor x = 4: 4*23 = 32; voor x = 3: 3*22 = 12, voor x = 2: 2*2 = 4. Het klopt als een zwerende vinger met wat je gevonden hebt. Maar, dit verband was lastig te vinden geweest door alleen naar het rijtje te kijken (denk ik).
[ Bericht % gewijzigd door motorbloempje op 01-09-2013 21:21:40 ]
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
En dit is dus gelijk aan de formule x * (2^x-1).
Mooi zeg Elegant.
Maar hoe kom jij van de sommatie naar de formule. Is dat een kleine stap?
Mooi zeg
Elegant.Maar hoe kom jij van de sommatie naar de formule. Is dat een kleine stap?
kloep kloep
Haakjes!
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Ik ben nu de huiswerk opdrachten even opnieuw aan het maken.
De wielgraaf W4, aantal opspannende bomen tellen. Dit werkte met subgroepen met spaken 1,2,3, 4 achtereenvolgens.
Wielgraaf heeft A in het midden, linksboven B, rechtsboven C, rechtsonder D en linksonder E.
k=1
2 mogelijkheden voor een boom:
1) pad van het type A-B-C-D-E 60 opties
2) boom A - B en dan een tak met E-D en een tak met -C. 60 opties.
Samen 120 mogelijke subbomen.
k=2
levert zelfde typen op die al geteld zijn.
je zou kunnen proberen een subboom te maken waarin beide spaken voorkomen maar dit levert óf een cykel óf het pad dat ik al heb geteld.
k=3
zelfde redenering als onder k=2. niets nieuws onder de zon
k=4
A is dan uniek, B,C, D en E uniek. Dus 5 nieuwe mogelijkheden als subboom.
Gevolg: 60+60+5=125.
De wielgraaf W4, aantal opspannende bomen tellen. Dit werkte met subgroepen met spaken 1,2,3, 4 achtereenvolgens.
Wielgraaf heeft A in het midden, linksboven B, rechtsboven C, rechtsonder D en linksonder E.
k=1
2 mogelijkheden voor een boom:
1) pad van het type A-B-C-D-E 60 opties
2) boom A - B en dan een tak met E-D en een tak met -C. 60 opties.
Samen 120 mogelijke subbomen.
k=2
levert zelfde typen op die al geteld zijn.
je zou kunnen proberen een subboom te maken waarin beide spaken voorkomen maar dit levert óf een cykel óf het pad dat ik al heb geteld.
k=3
zelfde redenering als onder k=2. niets nieuws onder de zon
k=4
A is dan uniek, B,C, D en E uniek. Dus 5 nieuwe mogelijkheden als subboom.
Gevolg: 60+60+5=125.
kloep kloep
Het maakt wel uit of je met een vaste labelling werkt of niet. Als je inderdaad altijd A in het midden hebt, neemt het aantal mogelijkheden af. Aangezien je rechtsboven C hebt en linksonder E, zul je nooit de lijn AE in je graaf kunnen hebben. Dat kan alleen als je labelling niet vaststaat en je AE buurpunten kunt maken.
Daher iſt die Aufgabe nicht ſowohl, zu ſehn was noch Keiner geſehn hat, als, bei Dem, was Jeder ſieht, zu denken was noch Keiner gedacht hat.
Het is een gelabelde graaf, ja. Labels liggen niet vast, het gaat puur om het aantal mogelijke bomen. A hoeft niet altijd het centrum te zijn. Bij k=4 zie je ook dat B,C,D, E als centrum kunnen fungeren.
Cayley zegt zelf ook dat het 53 =125 bomen moeten worden.
Cayley zegt zelf ook dat het 53 =125 bomen moeten worden.
kloep kloep
