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.
