Matematik
Side 2 - Att: Epsilon, Dominik Hazek, Duffy.
Svar #21
15. december 2005 af fixer (Slettet)
"Men frugtbar vej menes en vej der der tillader en større strøm gennem netværket."
->
Med en frugtbar vej menes en vej der tillader en større strøm gennem netværket.
Svar #22
15. december 2005 af Triangle (Slettet)
aha, mange tak.
Har du tid og lyst til at kigge den omtalte opgave fra i dag igennem?
Henrik
Svar #23
15. december 2005 af Triangle (Slettet)
Svar #24
15. december 2005 af fixer (Slettet)
Mht. opgaven kan den, om du vil, oploades på peecee.dk.
Svar #25
15. december 2005 af Triangle (Slettet)
Definition:
"I en sammenhængende graf G kaldes en delgraf G1 et skelet ellet et udspændende træ for G, hvis G1 er et træ, som indeholder samtlige punkter i G"
definition:
" Det skelet, som algoritmen i #8 frembringer, kaldes et økonomitræ"
mht peecee.dk, når jeg åbner siden, opstår der fejl på den. er det evt andre muligheder?
Svar #26
15. december 2005 af Triangle (Slettet)
Svar #28
15. december 2005 af fixer (Slettet)
Et minimalt træ er jo (jvf. #10) et udspændende træ med minimal vægtsum. Og da algoritmen i #8 frembringer et minimalt træ, følger af definitionen på økonomitræ i #25, at et økonomitræ er det samme som et minimalt træ.
Svaret på dit spørgsmål i #23 er derfor ja, med ovenstående begrundelse.
Mht. opgaven på peecee er den korrekt, dog skal du være opmærksom på en inkonsistens.
På side 1 oplyses begge de følgende strækninger
Kbh - Greve
Roskile - Køge
at have længden 25.7 km. Dog fremgår det ved valget af kant nummer 4 at afstanden Roskile - Køge er 26.5 km. Lykkeligvis har fejlen ikke nogen betydning for kantvalget, da denne netop dropper ud idet der dannes en kreds. Men du bør rette det.
Svar #29
15. december 2005 af Triangle (Slettet)
selvfølgelig, du har helt ret. Det er mig, der ikke er helt så opmærksom.
tak for ulejligheden.
I min læsning om træer, skelet og økonomitræ rejser sig endnu et spørgsmål. Jeg har en oversigt, der viser sammenhængen mellem antallet af punkter og antallet af træer. Jeg kan umiddelbart se at det ligner noget, der minder om en eksponentiel vækst. Ville det være nyttigt at påvise denne vækst (hvis der er tale om sådan en), ved at afbilde i et logaritmisk koordinatsystem, og derved få et voksende linær funktion?
Svar #30
15. december 2005 af fixer (Slettet)
Det var måske mere værd at overveje at ethvert træ med p punkter har p-1 kanter. Dette er et korollar til sætningen i #10 og følger øjeblikkeligt af punkt (2). Antallet af træer med p punkter må derfor have samme svar som spørgsmålet: "På hvor mange måder kan der så dannes p-1 kanter mellem p punkter?"
Det kan du jo overveje. Har dog ikke selv gjort mig nogle tanker.
Svar #31
15. december 2005 af Triangle (Slettet)
Men denne sammenhæng, som har en tabel over, viser antallet af forskellige træer som funktion af antallet n af punkter. Når man så finder en evt eksponentiel vækst mellem disse to størrelser har det jo ikke noget med beviset : "Et træ med n punkter har n-1 kanter" at gøre..? eller tage jeg helt fejl?
Svar #32
16. december 2005 af fixer (Slettet)
Såfremt du har en tabel kan følgende alternative fremgangsmåde benyttes:
Udfra tabellen opstilles et udsagn om sammenhængen mellem antallet af punkter, n, og antallet, P, af udspændende træer. Udsagnet kan være på formen
P(n): P = f(n), n >= 2
hvor f er den sammenhæng, du postulerer udfra tabellen.
Prøv dernæst om det ved induktion kan vises at P(n) er sand for alle naturlige tal n >= 2.
Svar #33
16. december 2005 af Triangle (Slettet)
Svar #35
16. december 2005 af Triangle (Slettet)
Svar #36
16. december 2005 af Triangle (Slettet)
Når man betragter en række fuldstændige grafer, opdager man, at der er en sammenhæng mellem antallet af punket n, der giver den pågældende graf navnet Kn, og antallet af kanter.
antallet af kanter kan findes ved :
n(n-1)/2. Jeg har så prøvet at gyldigheden af denne påstand ved at "teste" den på en række grafer. Dette passer hver gang, men er det nok i sig selv, til at acceptere denne påstand for sand?
Svar #37
16. december 2005 af fixer (Slettet)
Som nævnt i #30 skal du holde dig fra grafisk baserede konklusioner i matematisk sammenhæng.
Hvis ikke du kan komme op med et eksakt regneudtryk, kan der ikke laves et induktionsbevis.
#36
Jeg antager, at der med fuldstændig graf menes en graf, i hvilken alle punkter er forbundne med hinanden via en kant.
Idet P(n) er antal kanter i en fuldstændig graf med n punkter, er udsagnet
P(n) = n(n-1)/2 , n>=2
åbenbart sandt for n = 2, thi 2 punkter kan forbindes med netop 1 = 2(2-1)/2 = P(2) kanter.
Antag nu at P(n) er sand for et arbitrært n >=2 og vis at P(n)=>P(n+1). Det er et meget simpelt bevis.
Svar #38
16. december 2005 af Triangle (Slettet)
2(2-1)/2=2/2=1, korrekt?
men hvordan kan antallet af kanter,
P(n) være => p(n+1) ?
Svar #39
16. december 2005 af Triangle (Slettet)
Svar #40
16. december 2005 af fixer (Slettet)
I induktionsbeviser skal man endvidere være yderst påpasselig med hvilken vej man slutter.
Den korrekte måde at argumentere på er som angivet i #37. Med n=2 punkter kan der dannes netop een fuldstændig graf og dermed er udsagnet P(2) = 2(2-1)/2 = 1 sandt.
Du skal nu vise, at hvis P(n) er sand og vise at dette medfører, at så er også P(n+1) sand.
Betragt dertil en fuldstændig graf G(n) med n punkter. Hvis P(n) er sand har G(n) netop n(n-1)/2 kanter.
Til G(n) adderes nu eet punkt. G(n+1) fremkommer nu ved at forbinde det nye punkt med alle de øvrige n punkter i G(n). Dette giver anledning til præcist n nye kanter. Antallet i kanter i den fuldstændige graf G(n+1) er derfor
n(n-1)/2+n = ½(n^2-n+2n) = ½(n^2+n) = ½(n+1)n = P(n+1)
Da således P(2) og sand og da P(n) => P(n+1) sluttes af induktionsaksiomet, at så er P(n) sand for alle n >= 2.