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
Dat kan allemaal wel wat eenvoudiger dan met tekeningetjes (sowieso gevaarlijk om plaatjes als bewijs op te voeren).quote:Op woensdag 19 november 2008 20:43 schreef Borizzz het volgende:
Ik ben op zoek naar een grafentheoretisch bewijs. Ik zit er nu enkele dagen op te staren maar ik kan het nog niet oplossen. Het gaat over "bomen".
Een boom heeft 2 punten met graad 3. Bewijs dat de boom minstens 4 punten van graad 1 heeft.
Als ik dit ga tekenen, 2 punten met graad 3 dmv een brug aan elkaar verbinden, en dan de andere 4 punten een eindpunt laten worden dan is dit direct duidelijk; maar een bewijs is dit nog niet.
Wie kan helpen?
Als v het aantal knopen in de boom is en e het aantal kanten, dan is e = v - 1. Verder is de som van de graden van de knopen gelijk aan 2e. Stel nu dat d knopen zijn van graad 1. Er is gegeven dat er 2 punten met graad 3 zijn. De overige v-d-2 punten hebben dus graad minstens 2. Totaal van de graden komt hiermee uit op minstens
d + 6 + 2(v-d-2) = 2v - d + 2 = 2(e+1) - d + 2 = 2e - d + 4.
Maar het totaal van de graden is 2e, dus d is minstens 4.
Ik vind grafentheorie wel bij uitstek geschikt om plaatjes te maken. Jouw bewijs klopt natuurlijk (en is tamelijk elegant), maar als je het plaatje maakt zie je dat je die 2e - d + 4 krijgt vanwege de structuur van de graaf waarbij je altijd vier losse subboompjes hebt die vroeg of laat op een punt van graad 1 moeten uitkomen. Ook dat is niet helemaal mooi verwoord.quote:Op woensdag 19 november 2008 21:47 schreef thabit het volgende:
Dat kan allemaal wel wat eenvoudiger dan met tekeningetjes (sowieso gevaarlijk om plaatjes als bewijs op te voeren).
Maar enfin.
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 zie geen tegenstelling. Plaatjes zijn uitermate geschikt om inzicht te krijgen maar in bewijzen moet je ze mijden.quote:Op woensdag 19 november 2008 21:54 schreef Iblis het volgende:
[..]
Ik vind grafentheorie wel bij uitstek geschikt om plaatjes te maken. Jouw bewijs klopt natuurlijk (en is tamelijk elegant), maar als je het plaatje maakt zie je dat je die 2e - d + 4 krijgt vanwege de structuur van de graaf waarbij je altijd vier losse subboompjes hebt die vroeg of laat op een punt van graad 1 moeten uitkomen. Ook dat is niet helemaal mooi verwoord.
Hoe kan ik het aantal opspannende bomen van K5 vinden? Er zijn er teveel om zo te tekenen en ik moet onderscheid maken in 3 typen bomen. Hoe werkt dit en hoe komt ik dan aan het aantal opspannende bomen per type boom? De stelling van Cayley mag ik niet gebruiken hierbij...
Verdraaid lastig.
Verdraaid lastig.
kloep kloep
Als je begint dan zul je al wel zien dat er vanzelf types ontstaan. Je kunt een simpel pad hebben; je kunt een ster hebben; (maximaal graad 4 van 1 knoop) en je kunt een knoop met graad 3 hebben. Dan ben je al een aardig eindje op weg. Want hoe je graaf ook tekent, alle knopen zijn in principe symmetrisch.quote:
Hoe kan ik het aantal opspannende bomen van K5 vinden? Er zijn er teveel om zo te tekenen en ik moet onderscheid maken in 3 typen bomen. Hoe werkt dit en hoe komt ik dan aan het aantal opspannende bomen per type boom? De stelling van Cayley mag ik niet gebruiken hierbij...
Verdraaid lastig.
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.
Oke, dus kijken naar de graden van een aantal punten.
Mooi dat had ik nog niet eens gezien.
Dan verder: bijvoorbeeld de ster: 1 punt met graad 4, en 4 punten met graad 1. Als ik van deze boom uitga, dan is er toch maximaal 1 opspannende boom, nl de ster zelf?
K5 moet 125 opspannende bomen hebben en er zijn 3 types. Ik kom daar al tellend nooit op uit.
(doel is dit toepassen op K6, maar ik probeer eerst de manier te leren dmv K5).
Mooi dat had ik nog niet eens gezien.
Dan verder: bijvoorbeeld de ster: 1 punt met graad 4, en 4 punten met graad 1. Als ik van deze boom uitga, dan is er toch maximaal 1 opspannende boom, nl de ster zelf?
K5 moet 125 opspannende bomen hebben en er zijn 3 types. Ik kom daar al tellend nooit op uit.
(doel is dit toepassen op K6, maar ik probeer eerst de manier te leren dmv K5).
kloep kloep
Maar het maakt (voor een gelabelde graaf!) uit welk punt in het midden zit. De 'volgorde' van de punten van de ster is er niet. Maar:quote:
Oke, dus kijken naar de graden van een aantal punten.
Mooi dat had ik nog niet eens gezien.
Dan verder: bijvoorbeeld de ster: 1 punt met graad 4, en 4 punten met graad 1. Als ik van deze boom uitga, dan is er toch maximaal 1 opspannende boom, nl de ster zelf?
K5 moet 125 opspannende bomen hebben en er zijn 3 types. Ik kom daar al tellend nooit op uit.
(doel is dit toepassen op K6, maar ik probeer eerst de manier te leren dmv K5).
| 1 2 3 4 5 | | | | b-c-d d-c-e b-d-c | | | e a e |
De eerste twee zijn gelijk natuurlijk, maar de 3e is wel degelijk anders.
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.
Klopt dit dan voor K5:
Type 1: 1 punt met graad 4 en 4 punten met graad 1.
Dit type heeft een centrum. Voor een gelabelde graaf maakt het uit welk punt in het midden zit. Alle 5 punten kunnen in het centrum zitten. Er zijn dus 5 verschillende opspannende bomen.
Type 2: Drie punten graad 2, twee punten graad 2.
Dit is op één lijn na geen cykel. Ook hier maakt het weer uit welke punten graad 2 hebben en welke niet. Dit type heeft ook 5 mogelijkheden.
Type 3: 1 punt graad 3, 1 punt graad 2, 3 punten graad 1.
type 3 is een lijn met 4 punten en ergens een vertakking. Deze vertakking kan alleen bij de twee punten in het midden voorkomen. (Anders is het type 2). Dit type heeft ook 5 opspannende bomen.
Dit maakt samen 5x5x5=125 opspannende bomen voor K5.
Type 1: 1 punt met graad 4 en 4 punten met graad 1.
Dit type heeft een centrum. Voor een gelabelde graaf maakt het uit welk punt in het midden zit. Alle 5 punten kunnen in het centrum zitten. Er zijn dus 5 verschillende opspannende bomen.
Type 2: Drie punten graad 2, twee punten graad 2.
Dit is op één lijn na geen cykel. Ook hier maakt het weer uit welke punten graad 2 hebben en welke niet. Dit type heeft ook 5 mogelijkheden.
Type 3: 1 punt graad 3, 1 punt graad 2, 3 punten graad 1.
type 3 is een lijn met 4 punten en ergens een vertakking. Deze vertakking kan alleen bij de twee punten in het midden voorkomen. (Anders is het type 2). Dit type heeft ook 5 opspannende bomen.
Dit maakt samen 5x5x5=125 opspannende bomen voor K5.
kloep kloep
Ik neem aan dat je bij type 2 twee punten met graad 1 bedoelt. Maar, je berekening is hoogst dubieus en gaat duidelijk naar het antwoord toe, daar het bij type 2 en type 3 om heel andere aantallen gaat.
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 ik weet; maar ik heb geen idee hoe ik bijv. het aatal bomen van bijv. type 2 anders zou kunnen vinden.
kloep kloep
Type 2 is b.v.:quote:
Ja ik weet; maar ik heb geen idee hoe ik bijv. het aatal bomen van bijv. type 2 anders zou kunnen vinden.
| 1 |
Of:
| 1 |
Bedenk, de boom is gelabelled, en er is natuurlijk geen enkele manier waarop je louter door draaien, spiegelen, of wat dan ook de eerste in de tweede kunt doen laten overgaan.
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.
Zitten A en E dan vast op het uiteinde?
Volgens mij moet er dan heel veel mogelijk zijn:
abcde
acdeb
adebc
aebcd
bceda
cdeab
ceabe etc
dat wordt 5x4x3x2x1 = 120 mogelijkheden.
Maar dat kan natuurlijk nooit goed zijn.
Volgens mij moet er dan heel veel mogelijk zijn:
abcde
acdeb
adebc
aebcd
bceda
cdeab
ceabe etc
dat wordt 5x4x3x2x1 = 120 mogelijkheden.
Maar dat kan natuurlijk nooit goed zijn.
kloep kloep
En 120 is dus te veel, want je kunt: a-b-c-d-e en e-d-c-b-a moeilijk verschillend noemen. Dat is gewoon hoe je ze tekent (en daar heeft thabit op zich wel gelijk, dat plaatjes verraderlijk zijn misschien).
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 daar kom ik nog niet verder mee.
Als ik bv A en E als uiteinde neem, zijn BCD in het midden. Dit kan op 2 manieren
Als ik B en C als uiteinde neem, zitten ADE in het midden. Ook 2 manieren
Als ik D en A als uiteinde neem zitten CBE in het midden. Ook 2 manieren.
Moet het op deze manier?
Als ik bv A en E als uiteinde neem, zijn BCD in het midden. Dit kan op 2 manieren
Als ik B en C als uiteinde neem, zitten ADE in het midden. Ook 2 manieren
Als ik D en A als uiteinde neem zitten CBE in het midden. Ook 2 manieren.
Moet het op deze manier?
kloep kloep
Als je A en E als uiteinde neemt heb je:
ABCDE
ABDCE
ACBDE
ACDBE
ADBCE
ADCBE
6 mogelijkheden dus. Immers, elk van die mogelijkheden is wel degelijk anders. In het eerste geval heeft B als buren A en C; dat heeft het nergens anders in deze 6 mogelijkheden. Kortom, ze zijn anders. Anders gesteld, je kunt ook met je 120 beginnen en daar het aantal mogelijkheden dat je dubbel telt vanaf trekken, en als je even nadenkt heb je zo door welke symmetrie daar een rol speelt; anderzijds kun je ook zo verder gaan en bedenken op hoeveel manieren je een uiteinde kunt kiezen.
ABCDE
ABDCE
ACBDE
ACDBE
ADBCE
ADCBE
6 mogelijkheden dus. Immers, elk van die mogelijkheden is wel degelijk anders. In het eerste geval heeft B als buren A en C; dat heeft het nergens anders in deze 6 mogelijkheden. Kortom, ze zijn anders. Anders gesteld, je kunt ook met je 120 beginnen en daar het aantal mogelijkheden dat je dubbel telt vanaf trekken, en als je even nadenkt heb je zo door welke symmetrie daar een rol speelt; anderzijds kun je ook zo verder gaan en bedenken op hoeveel manieren je een uiteinde kunt kiezen.
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.
Oke, met AB, AC, AD, AE, BC, BD, BE, CD, CE en DE als uiteinden. Dit levert 10x6=60 verschillende mogelijkheden voor type 2.
Type 1 had er 5. dus voor type 1 en 2 samen 65. Klopt dit.
Type 1 had er 5. dus voor type 1 en 2 samen 65. Klopt dit.
kloep kloep
Ja. Als je het berekent kun je stellen: Je hebt (5 boven 2) = 10 keuzes voor de uiteinden en dan 3! = 6voor erbinnenin, dat geeft 10 * 6 = 60. Of je hebt 5! voor het geheel, maar omdat het niet uitmaakt wat je als voor of achteraan beschouwt tel je ze dubbel, ofwel 120/2 = 60.quote:
Oke, met AB, AC, AD, AE, BC, BD, BE, CD, CE en DE als uiteinden. Dit levert 10x6=60 verschillende mogelijkheden voor type 2.
Type 1 had er 5. dus voor type 1 en 2 samen 65. Klopt dit.
Nu type 3: daar moet je ook even goed kijken welke knopen in feite dezelfde rol spelen.
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, voor type 3 kan ik dan hetzelfde doen. Nu zijn de uiteinden van type 2 de middens van type 3 geworden.
Nu k6. Ik heb de voldende typen onderscheiden:
Type 1: 1 punt met graad 5, 5 punten met graad 1 -> 6 mogelijkheden
Type 2: 1 punt met graad 4, 3 punten met graad 2, 2 punten met graad 1
Type 3: 2 punten met graad 4, 2 punten met graad 2, 2 punten met graad 1.
Type 4: 2 punten met graad 3, 4 punten met graad 2
Type 5: 4 punten met graad 3, 2 punten met graad 2
Type 6: 5 punten met graad 2
Nu k6. Ik heb de voldende typen onderscheiden:
Type 1: 1 punt met graad 5, 5 punten met graad 1 -> 6 mogelijkheden
Type 2: 1 punt met graad 4, 3 punten met graad 2, 2 punten met graad 1
Type 3: 2 punten met graad 4, 2 punten met graad 2, 2 punten met graad 1.
Type 4: 2 punten met graad 3, 4 punten met graad 2
Type 5: 4 punten met graad 3, 2 punten met graad 2
Type 6: 5 punten met graad 2
kloep kloep
Als ik type 2 even teken krijg ik daar een cykel in? Idem voor type 3? Twee punten met graad 4 (neem aan dat ze buren van elkaar zijn) 8 punten, tenzij er een paar lussen inzitten. En we hebben het over K6? Slinger desnoods paint even aan om een paar schetsjes te maken en hier te tonen, want dit is toch wel erg raar.
Ook met je andere typen heb ik aardig wat problemen. En 5 punten met graad 2 lijkt me een Cykel op 5 punten geven. Sowieso geen boom, en geen 6 punten.
Ook met je andere typen heb ik aardig wat problemen. En 5 punten met graad 2 lijkt me een Cykel op 5 punten geven. Sowieso geen boom, en geen 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.
Dan vind ik in het begin dit:
Deze graaf is onder te verdelen in verschillende typen.
Type 1: 1 punt met graad 5, 5 punten met graad 1.
Voor dit type zijn 6 opspannende bomen mogelijk.
Type 2: 1 punt met graad 4, 3 punten met graad 2, 2 punten met graad 1.
(6! /(3!*2!) = 60 mogelijke keuzes 3 keuzes voor punten met graden 2 en 4. Dan kan ik de punten met graad 3 op 3! Manieren rangschikken en de punten met graad 2 op 2! Manieren. Dus 60*2!*3! Is 720 mogelijke manieren voor type 2.
Maar dan ben ik al snel bij de 1296 mogelijkheden voor K6. Dusook hier klopt weer iets niet.
Deze graaf is onder te verdelen in verschillende typen.
Type 1: 1 punt met graad 5, 5 punten met graad 1.
Voor dit type zijn 6 opspannende bomen mogelijk.
Type 2: 1 punt met graad 4, 3 punten met graad 2, 2 punten met graad 1.
(6! /(3!*2!) = 60 mogelijke keuzes 3 keuzes voor punten met graden 2 en 4. Dan kan ik de punten met graad 3 op 3! Manieren rangschikken en de punten met graad 2 op 2! Manieren. Dus 60*2!*3! Is 720 mogelijke manieren voor type 2.
Maar dan ben ik al snel bij de 1296 mogelijkheden voor K6. Dusook hier klopt weer iets niet.
kloep kloep
Maar idd er zit een cykel in. Niet bij stilgestaan.
Maar op welke systematische manier krijg ik dan alle typen van K6 wel bij elkaar?
kloep kloep
Teken type 2 eens! 1 punt met graad 4 betekent dat je al 5 punten hebt gedefinieerd. Daarvan hebben dus ook nog 3 punten (minstens) graad twee, dus komen er nog eens 3 punten = 8 punten in totaal bij. Zodra je een punt dat je al hebt 'hergebruikt' heb je een cykel en heb je geen boom meer! Ik zie niet hoe je dit doet.
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.
Gewoon tekenen. Je bent al begonnen met een punt met graad 5, dat is zoiets:quote:
[ afbeelding ]
Maar idd er zit een cykel in. Niet bij stilgestaan.
Maar op welke systematische manier krijg ik dan alle typen van K6 wel bij elkaar?
| 1 2 3 4 5 | \ / d /|\ a b c |
Dan begin je eerst eens een punt met graad 4 te tekenen. Dan heb je zoiets:
| 1 2 3 4 5 | \ / d / \ a c |
En nu moet je knoop b nog ergens kwijt. Dat kan niet aan d, want dan heb je de situatie die je net al had, dus moet het aan een van de andere (maar dat is in feite symmetrisch) dus je krijgt altijd zo'n soort kruis:
| 1 2 3 4 5 6 7 | | b-c-d | e | f |
Het maakt hier dus uit welk punt op de plek van c zit, en welk punt op de plek van e zit.
Nu doe je hetzelfde voor de rest, maar dan begin je met een knoop met graad 3… en dan ga je weer kijken wat er kan gebeuren (hint: 3 typen), en dan uiteindelijk met een graaf met knopen met maximaal graad 2 (altijd een pad graaf).
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 kom dan in totaal aan 6 typen.
type 1: 1 punt met graad 5, 5 punten met graad 1. Totaal 6 mogelijkheden.
type 2: 1 punt met graad 4, 1 punt met graad 2, 4 punten met graad 1. Dit is het kruis dat al eerder getekend werd. Dit heeft 6! / 4! = 30 mogelijkheden.
type 3: 2 punten met graad 3, 4 punten met graad 1. Lijkt op de letter H. Totaal 6! / (4! * 2! ) = 15 mogelijkheden.
type 4: 1 punt met graad 3, 2 punten met graad 2, 3 punten met graad 1. Geeft 6! ( 3! * 2!) = 60 mogelijkheden.
type 5: 1 punt met graad 3, 2 punten met graad 2, 3 punten met graad 1. Lijkt op type 4, maar deze kan ook anders getekend worden. Ook 60 mogeljkheden dus.
type 6: 4 punten met graad 2, 2 punten met graad 1. Dus idd een pad. 6! / (4!*2!) is = 15 mogelijkheden.
Klopt dit. Volgens mij rammelt het mogelijkheden uitrekenen nog wat.
type 1: 1 punt met graad 5, 5 punten met graad 1. Totaal 6 mogelijkheden.
type 2: 1 punt met graad 4, 1 punt met graad 2, 4 punten met graad 1. Dit is het kruis dat al eerder getekend werd. Dit heeft 6! / 4! = 30 mogelijkheden.
type 3: 2 punten met graad 3, 4 punten met graad 1. Lijkt op de letter H. Totaal 6! / (4! * 2! ) = 15 mogelijkheden.
type 4: 1 punt met graad 3, 2 punten met graad 2, 3 punten met graad 1. Geeft 6! ( 3! * 2!) = 60 mogelijkheden.
type 5: 1 punt met graad 3, 2 punten met graad 2, 3 punten met graad 1. Lijkt op type 4, maar deze kan ook anders getekend worden. Ook 60 mogeljkheden dus.
type 6: 4 punten met graad 2, 2 punten met graad 1. Dus idd een pad. 6! / (4!*2!) is = 15 mogelijkheden.
Klopt dit. Volgens mij rammelt het mogelijkheden uitrekenen nog wat.
kloep kloep
Type 4 is zeg maar het kruis, maar dan heb je de top onderaan gehangen:
Ofwel een T.
En type 5 is juist het kruis maar dan van de 'zijkant' (dit is relatief natuurlijk) eentje weggehaalt en bovenop gezet:
Mij helpt het een stuk als je zulke tekeningetjes maakt, want dan weet ik dat we het over hetzelfde hebben! Maar goed, los daarvan… je berekeningen van de aantallen kloppen absoluut niet inderdaad. Bijvoorbeeld type 5. Je neemt 1 punt voor plek d (6 mogelijkheden) dan is de rest het aantal dat je bij het vorige probleem al had opgelost: namelijk 60. Ofwel: 6 * 60 = 360.
Denk hier nog eens goed over na, en vertel anders even waarom je op de aantallen en de manier van berekeningen uitkomt als je komt. Gebruik die plaatjes, zeg b.v. "er zijn voor d zes mogelijkheden, en dan voor de rest", etc. Dan kan ik aanwijzen waar je fout gaat in je redeneringen.
[ Bericht 12% gewijzigd door Iblis op 20-11-2008 18:39:11 ]
| 1 2 3 4 5 6 7 | | e | f | a |
Ofwel een T.
En type 5 is juist het kruis maar dan van de 'zijkant' (dit is relatief natuurlijk) eentje weggehaalt en bovenop gezet:
| 1 2 3 4 5 6 7 8 9 | | a | c-d | e | f |
Mij helpt het een stuk als je zulke tekeningetjes maakt, want dan weet ik dat we het over hetzelfde hebben! Maar goed, los daarvan… je berekeningen van de aantallen kloppen absoluut niet inderdaad. Bijvoorbeeld type 5. Je neemt 1 punt voor plek d (6 mogelijkheden) dan is de rest het aantal dat je bij het vorige probleem al had opgelost: namelijk 60. Ofwel: 6 * 60 = 360.
Denk hier nog eens goed over na, en vertel anders even waarom je op de aantallen en de manier van berekeningen uitkomt als je komt. Gebruik die plaatjes, zeg b.v. "er zijn voor d zes mogelijkheden, en dan voor de rest", etc. Dan kan ik aanwijzen waar je fout gaat in je redeneringen.
[ Bericht 12% gewijzigd door Iblis op 20-11-2008 18:39:11 ]
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.
Nou we zijn het eens over de 6 mogelijke typen. Die had ik ook gevonden.
Maar ik heb wat moeite met het vinden van de mogelijkheden per type. Dat is wat combinatoriek en dat is voor mij lang geleden.
Type 2 doe ik bv zo. Dit type heeft 4 punten met graad 1, 1 punt met graad 4 en 1 punt met graad 2. Dit kan ik als volgt noteren: 111142.
Dus 6! / 4!*2! volgorden om dit op te schrijven. Volgens mij heb ik dat op deze manier ooit geleerd.
Of pak je zoiets totaal anders aan?
Maar ik heb wat moeite met het vinden van de mogelijkheden per type. Dat is wat combinatoriek en dat is voor mij lang geleden.
Type 2 doe ik bv zo. Dit type heeft 4 punten met graad 1, 1 punt met graad 4 en 1 punt met graad 2. Dit kan ik als volgt noteren: 111142.
Dus 6! / 4!*2! volgorden om dit op te schrijven. Volgens mij heb ik dat op deze manier ooit geleerd.
Of pak je zoiets totaal anders aan?
kloep kloep
Nee, totaal anders. Je moet kijken welke punten equivalent zijn, en dat betekent wel dat ze dezelfde graad hebben, maar niet per se. Dat is noodzakelijk, maar niet voldoende:
Neem type 2. Eerst doe ik een wat omslachtiger methode, maar enfin: punt c is 'uniek'. Punt a/b/d zijn echter equivalent. Als je a met b verwisselt in de tekening heb je geen nieuwe graaf. c heeft dan nog steeds als buren a, b, d, e. Dus daar verandert niets aan. Verwissel je echter a met f dan heb je wél een nieuwe graaf, want dan heeft c als buren f, b, d, e. Het gaat dus niet zo maar om de graad! Zo valt dus te zien dat a, b, d compleet verwisselbaar zijn. Het maakt niet uit in welke volgorde je daar die drie knopen stopt, alleen wélke drie. Nadat het middelste punt gekozen is (6 mogelijkheden) zijn er nog (5 boven 3) mogelijkheden om punten voor de zojuist genoemde posities te kiezen. Dan houd je nog 2 labels over voor de punten 'onderaan'. De volgorde van deze twee maakt uit natuurlijk. Dus, dat geeft in totaal: 6 * (5 boven 3) * 2! mogelijkheden = 6 * 5!/3! = 6 * 5 * 4 = 120 mogelijkheden.
Je kunt natuurlijk ook via een andere volgorde werken. Je kunt ook zeggen: Ik label eerst het pad dat hier als c,e,f staat: dat geeft me 6*5*4 mogelijkheden = 120. De drie punten die ik dan nog overhoud zijn allemaal symmetrisch dus de volgorde van toekenning maakt niet uit. Weer 120 mogelijkheden.
Je moet hier dus goed in de gaten houden welke punten 'verwisselbaar' zijn, en welke niet.
| 1 2 3 4 5 6 7 | | b-c-d | e | f |
Neem type 2. Eerst doe ik een wat omslachtiger methode, maar enfin: punt c is 'uniek'. Punt a/b/d zijn echter equivalent. Als je a met b verwisselt in de tekening heb je geen nieuwe graaf. c heeft dan nog steeds als buren a, b, d, e. Dus daar verandert niets aan. Verwissel je echter a met f dan heb je wél een nieuwe graaf, want dan heeft c als buren f, b, d, e. Het gaat dus niet zo maar om de graad! Zo valt dus te zien dat a, b, d compleet verwisselbaar zijn. Het maakt niet uit in welke volgorde je daar die drie knopen stopt, alleen wélke drie. Nadat het middelste punt gekozen is (6 mogelijkheden) zijn er nog (5 boven 3) mogelijkheden om punten voor de zojuist genoemde posities te kiezen. Dan houd je nog 2 labels over voor de punten 'onderaan'. De volgorde van deze twee maakt uit natuurlijk. Dus, dat geeft in totaal: 6 * (5 boven 3) * 2! mogelijkheden = 6 * 5!/3! = 6 * 5 * 4 = 120 mogelijkheden.
Je kunt natuurlijk ook via een andere volgorde werken. Je kunt ook zeggen: Ik label eerst het pad dat hier als c,e,f staat: dat geeft me 6*5*4 mogelijkheden = 120. De drie punten die ik dan nog overhoud zijn allemaal symmetrisch dus de volgorde van toekenning maakt niet uit. Weer 120 mogelijkheden.
Je moet hier dus goed in de gaten houden welke punten 'verwisselbaar' zijn, en welke niet.
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.
Met 5 boven 3 bedoel je toch 5! / ( 3! * 2! ).
Ik heb die definitie van x boven y niet gehad vroeger, maar juist faculteiten.
maar als het middelste punt gekozen is, dan zijn er nog 5 plekken te vergeven. 3 zijn er equivalent en 2 niet. Geef volgens mij dus 5! /( 3! * 2! ) mogelijkheden?. Hier komt 10 uit. Dus ik zou zeggen in totaal 6 * 10 = 60 mogelijkheden.....
Ik heb die definitie van x boven y niet gehad vroeger, maar juist faculteiten.
maar als het middelste punt gekozen is, dan zijn er nog 5 plekken te vergeven. 3 zijn er equivalent en 2 niet. Geef volgens mij dus 5! /( 3! * 2! ) mogelijkheden?. Hier komt 10 uit. Dus ik zou zeggen in totaal 6 * 10 = 60 mogelijkheden.....
kloep kloep
Als het middelste punt gekozen is zijn er nog 5 te vergeven ja. Maar als je de labels voor de eerste 3 kiest, liggen die voor de andere 2 vast. Voor de eerste heb je (5 boven 3) = 5!/(2!3!) mogelijkheden. Dit is 'kiezen zonder herhaling, volgorde niet van belang'. Dus dat is inderdaad wat jij zegt.quote:
Met 5 boven 3 bedoel je toch 5! / ( 3! * 2! ).
Ik heb die definitie van x boven y niet gehad vroeger, maar juist faculteiten.
maar als het middelste punt gekozen is, dan zijn er nog 5 plekken te vergeven. 3 zijn er equivalent en 2 niet. Geef volgens mij dus 5! /( 3! * 2! ) mogelijkheden?. Hier komt 10 uit. Dus ik zou zeggen in totaal 6 * 10 = 60 mogelijkheden.....
De groep van twee echter is ook niet equivalent (je zou dus ook kunnen stellen dat je een groep van 3, en 2 groepen van 1 moet kiezen); het maakt uit welke helemaal 'onderaan' het kruis komt, en welke erboven. Dus de volgorde van die twee elementen maakt wél uit. Dat geeft de 2!. Dus het totaal is: 6 * 5!/(3!2!) * 2! = 6 * 5!/3! = 6 * 5 * 4 = 120.
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.
Akkoord. Het is stof die lang geleden is combineren met iets nieuws.
Nu ga ik type 3 eens proberen.
2 groepen punten: een groep van 4 punten die equivalent zijn en een groep van 2 punten die equivalent zijn.
Het gaat erom op hoeveel mogelijkheden 6 punten in groepen van 4 en 2 kunnen worden verdeeld.
Is dat niet ! / (4! * 2! ) = 15 mogelijkheden?
Nu ga ik type 3 eens proberen.
2 groepen punten: een groep van 4 punten die equivalent zijn en een groep van 2 punten die equivalent zijn.
Het gaat erom op hoeveel mogelijkheden 6 punten in groepen van 4 en 2 kunnen worden verdeeld.
Is dat niet ! / (4! * 2! ) = 15 mogelijkheden?
kloep kloep
Ik neem aan dat je indeling zodanig is dat de groep van 2 de punten met graad 3 zijn. Maar, stel dat je die twee punten a en b labelt, dan maakt het uit of je c/d de buren van a maakt of dat je c/d de buren van b maakt. In die zin zijn die vier punten niet geheel equivalent. Er zit een zekere symmetrie in die graaf, maar niet op deze manier.
Als je begint te labellen met die punten van 2, dan maakt het niet uit of je ze 'a b' of 'b a' labelt: dat is equivalent. Maar, nadát je ze gelabeld hebt maakt het wel iets uit.
Als je begint te labellen met die punten van 2, dan maakt het niet uit of je ze 'a b' of 'b a' labelt: dat is equivalent. Maar, nadát je ze gelabeld hebt maakt het wel iets uit.
SPOILEROm spoilers te kunnen lezen moet je zijn ingelogd. Je moet je daarvoor eerst gratis Registreren. Ook kun je spoilers niet lezen als je een ban hebt.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.
Iblis: bedankt voor je hulp hoor. Iets nieuws combineren met ver weggezakte stof is behoorlijk lastig. Maar geduld en je komt er wel. Zo is het ook gelukt met complexe functies. Tentamen was inderdaad een eitje.
Maar ik moet zeggen dat ik het prettig vind dat je met mij samen de denkstappen doorneemt en niet gewoon de antwoorden. Daarom is de spoiler jammer. Samen met een kundige naar het antwoord toewerken werkt beter voor mij. Maar goed, aangezien je weg moet
Maar ik moet zeggen dat ik het prettig vind dat je met mij samen de denkstappen doorneemt en niet gewoon de antwoorden. Daarom is de spoiler jammer. Samen met een kundige naar het antwoord toewerken werkt beter voor mij. Maar goed, aangezien je weg moet
kloep kloep
Nou, ik ben er weer; het is inderdaad niet het beste, maar de spoiler leek me duidelijk genoeg dat ik daarin wat zou verklappen. 
Het idee is hetzelfde verder, alhoewel er soms meerdere manieren zijn om het antwoord te beredeneren.
Het idee is hetzelfde verder, alhoewel er soms meerdere manieren zijn om het antwoord te beredeneren.
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 het het antwoord inmiddels zelf helemaal uitgewerkt. Maar ik blijf die combinatorische mogelijkheden uitrekenen lastig vinden. Is daar geen stoomcursus ofzo voor ergens?
Maar nog de wielgraaf W4, en het aantal opspannende bomen daarvan.
Ik heb ee hint gekregen dat je moet werken met subgroepen met k spaken met k=1,2,3,4. Maar ik kom daar nog geen stap verder mee omdat ik niet begrijp wat er bedoeld wordt.
Maar nog de wielgraaf W4, en het aantal opspannende bomen daarvan.
Ik heb ee hint gekregen dat je moet werken met subgroepen met k spaken met k=1,2,3,4. Maar ik kom daar nog geen stap verder mee omdat ik niet begrijp wat er bedoeld wordt.
kloep kloep
Maar, W4 is dat inclusief centrum of niet? Want W4 is K4 zou ik zeggen.
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.
Nou W3 is een volledige graaf dus exclusief centrum.
W4 heeft dan een centrum met erom heen 4 punten en 4 spaken.
De vraag gaat om een oplossing voor W4 en W5.... Te beginnen maar met W4...
W4 heeft dan een centrum met erom heen 4 punten en 4 spaken.
De vraag gaat om een oplossing voor W4 en W5.... Te beginnen maar met W4...
kloep kloep
Okay, W4 heeft dus 5 punten in totaal. Wat ik dan denk dat ze bedoelen is dat je eerst eens moet kijken naar het aantal bomen met maar 1 spaak erin. Dan het aantal met twee spaken erin, dan met drie, en dan met alle vier spaken.
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.
Dat had ik idd al bedacht. Het gaat om gelabelde bomen.
Dus als er 1 spaak is:
-A in het centrum, B verbonden met A (dat is dus de spaak) en D, E en C zijn equivalent.
Aantal opspannende bomen 5 * (4 boven 3) ??
Ik kies eerst een centrum, 5 mogelijkheden daarvoor. Dan heb ik er nog 4 over, waarbij 3 equivalent en 1 niet.
Dus als er 1 spaak is:
-A in het centrum, B verbonden met A (dat is dus de spaak) en D, E en C zijn equivalent.
Aantal opspannende bomen 5 * (4 boven 3) ??
Ik kies eerst een centrum, 5 mogelijkheden daarvoor. Dan heb ik er nog 4 over, waarbij 3 equivalent en 1 niet.
kloep kloep
Twee spaken: 2 punten met graad 3, 3 punten met graad 2.
D en E equivalent, A centrum dat zijn de punten met graad 2. B en C hebben dan graad 3.
Ik heb nog steeds geen idee hoe hier het aantal bomen kan worden berekend.
D en E equivalent, A centrum dat zijn de punten met graad 2. B en C hebben dan graad 3.
Ik heb nog steeds geen idee hoe hier het aantal bomen kan worden berekend.
kloep kloep
Probeer eerst eens vast te stellen wat de vorm van de boom is met maar één spaak erin. (Of vormen)quote:
Dat had ik idd al bedacht. Het gaat om gelabelde bomen.
Dus als er 1 spaak is:
-A in het centrum, B verbonden met A (dat is dus de spaak) en D, E en C zijn equivalent.
Aantal opspannende bomen 5 * (4 boven 3) ??
Ik kies eerst een centrum, 5 mogelijkheden daarvoor. Dan heb ik er nog 4 over, waarbij 3 equivalent en 1 niet.
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 schreef:
En een boom heeft geen cykels…quote:Maar nog de wielgraaf W4, en het aantal opspannende bomen daarvan.
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.
nou dan zou ik er dit van kunnen maken?
Uitgaande van een W4 met A als centrum en vier spaken naar B,C, D en E
A-B-C-D-E
Een pad dus. En die heeft 5! nogelijkheden.
Uitgaande van een W4 met A als centrum en vier spaken naar B,C, D en E
A-B-C-D-E
Een pad dus. En die heeft 5! nogelijkheden.
kloep kloep
Twee spaken:
A - B
|
D - E - C
Maar levert dat niet ook hetzelfde pad weer op.
Drie spaken
B - A - E - C
|
D
Vier spaken
B
|
D - A - C
|
E
A - B
|
D - E - C
Maar levert dat niet ook hetzelfde pad weer op.
Drie spaken
B - A - E - C
|
D
Vier spaken
B
|
D - A - C
|
E
kloep kloep
Een pad kan. Je telt wel weer dubbel. Want deze is niet anders dan de labelling met E in het centrum en B C D E op de hoeken. Maar er kan nog meer dan een pad. We zitten hier niet met een maximale graad, dus als je spaak A B pakt kun je beide buren van B opnemen in je boom.quote:
nou dan zou ik er dit van kunnen maken?
Uitgaande van een W4 met A als centrum en vier spaken naar B,C, D en E
A-B-C-D-E
Een pad dus. En die heeft 5! nogelijkheden.
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.
Hmm.. ik zie niet in waar ik dubbel tel.
Bij vier spaken (hierboven) moeten B en E aan de A vastzitten. Maar dat komt niet goed in mijn post terecht...
Bij vier spaken (hierboven) moeten B en E aan de A vastzitten. Maar dat komt niet goed in mijn post terecht...
kloep kloep
We hebben een graaf als deze dus:quote:
Hmm.. ik zie niet in waar ik dubbel tel.
Bij vier spaken (hierboven) moeten B en E aan de A vastzitten. Maar dat komt niet goed in mijn post terecht...
| 1 2 3 4 5 | |\ /| | o | |/ \| o---o |
Even nog zonder labels. We kunnen hier een pad in vinden met één spaak door in het centrum te beginnen en dan naar een hoekpunt te gaan (ongeacht welke) en dan b.v. linksom of rechtsom te gaan. Dat levert het volgende labelloze pad op: o--o--o--o--o
Stel dat in het centrum A staat en we naar linkboven gaan, waar B staat, en dan rechtsom, C, D, E. Dan hebben we de opspannende boom: A--B--C--D--E.
Stel echter in het centrum E staat, en we naar linksboven gaan, waar D staat, en dan rechtsom, C, B, A. Dan hebben we de opspannende boom: E--D--C--B--A. Volstrekt identiek dus. Terwijl ze volgens jouw manier van berekenen elk apart worden meegeteld.
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.
| Forum Opties | |
|---|---|
| Forumhop: | |
| Hop naar: | |