Matematik
Att: Epsilon, Dominik Hazek, Duffy.
Jeg sidder med en opgave under det matematiske område, diskret matematik.
Jeg skal i en opgave finde afstanden mellem nogle byer og dernæst konstruere et minimalt træ for disse byer. Da denne opgave er af stor betydning, vil jeg meget gerne løse den korrekt.
Jeg vil derfor tillade mig at spørge, om der evt. var nogen af jer, som ville kigge på mit løsningsforslag og kommentere det?
På forhånd tak.
Svar #1
14. december 2005 af Dominik Hasek (Slettet)
Svar #4
14. december 2005 af Triangle (Slettet)
Jeg er i gang med at lægge en sidste hånd på opgaven, men så snart jeg er færdig med dem, skal jeg gerne sende dig dem.
Svar #5
14. december 2005 af Dominik Hasek (Slettet)
Svar #6
14. december 2005 af Triangle (Slettet)
Hvis du kan nå det til og med mandag formiddag vil det være ganske fordelagtigt. Og rigtig god opgaveskrivning til dig :)
Svar #7
14. december 2005 af fixer (Slettet)
Svar #8
14. december 2005 af Triangle (Slettet)
Se, jeg sidder nemlig med en engelsk matematik bog, der netop omhandler mit emne. Og heri findes Kruskals algoritme nemlig også.
Men jeg må ærligt indrømme, at jeg ikke helt forstår gennemgangen af Kruskals algoritme.
Jeg har derimod fået en algortime til konstruktion af et økonomitræ T for en graf, udleveret:
1.Vælg som første kant e1 i T en kant med mindst værdi i G
2. Vælg som anden kant e2 i T en af de resterende kanter i G med mindst værdi.
3. Vælg som næste kan i T en af de resterende kanter i G med mindst værdi således, at den valgte kant ikke danner nogen lukket kæde med de allerede valgte kanter.
4. Fortsæt med at vælge kanter til T på denne måde, indtil et skelet er opnået, dvs indtil der er valgt n -1 kanter.
Lige det sidste er jeg ikke helt med på; dvs indtil der er valgt n-1 kanter? kan De evt. (venligst) forklare dette?
Svar #10
14. december 2005 af fixer (Slettet)
Definition 1:
Et træ er en sammenhængende graf, der ikke indeholder nogen kreds.
hvoraf følger (bevis udelades):
Lad T være en graf uden sløjfer med P punkter og K kanter. Da er følgende udsagn ensbetydende:
a) T er et træ.
b) To vilkårlige punkter i T er forbundet med netop een vej.
c) T er sammenhængende og P = K + 1
d) T er kredsfri
[hvis to endepunkter for en kant er sammenfaldende kaldes den en sløjfe].
Definition 2:
Et træ siges at udspænde en graf dersom det indeholder alle grafens punkter.
Definition 3:
Et minimalt træ er et udspændende træ med minimal vægtsum.
Et minimalt træ T for en graf G indeholder altså alle punkter P(G) i grafen forbundet med netop de kanter, der gør vægtsummen mindst mulig, og således at der ikke opstår nogen kreds.
Din algoritme vil føre til et minimalt træ, thi
1) Der opstår aldrig nogen kreds, idet kanter der ville danne kreds, udelades. Algoritmen producerer derfor et træ
2) Alle grafens punkter medtages idet træet vil få n-1 kanter hvilket sikrer - ifølge sætningen ovenfor - at alle grafens n punkter medtages.
3) Vægtsummen bliver minimal da der stedse vælges kanten med laveste vægt.
Svar #11
14. december 2005 af fixer (Slettet)
Der kan ikke subskriberes på bestemte brugeres hjælp. Al hjælp er frivillig.
Svar #12
14. december 2005 af Triangle (Slettet)
det hjalp betydeligt på forståelsen, tak for det.
MEN, jeg er stadig ikke helt med på formuleringen, n-1 kanter?
Og denne vægtsummen, hvis jeg har forstået det korrekt, så er det altså summen af værdierne for alle de kanter, som G indeholder? og i mit tilfælde vil det så være antal km, da det er afstanden mellem byer jeg skal finde?
Svar #13
14. december 2005 af Triangle (Slettet)
Nej, det har du helt ret i. Men eftersom diskret matematik gennemgås på matematik-studiet og som regel ikke på gymnasiet, antog jeg at de omtalte navne måske ville have en bedre chance for at hjælpe, da jeg på daværende tidspunkt kun kendte til Epsilon og Dominik Hazek, der studerede matematik. Men det viser sig så, at her er også brugere, der har alsluttet et matematisk studie. ;-)
I den anledning vil jeg lige sige tak for at du stiller din viden til rådighed.
Svar #14
14. december 2005 af fixer (Slettet)
Lad os sige at der er N byer. Grafen, der fremkommer ved indtegning af vejene mellem byerne, har således N punker og et vist antal, K, kanter (=veje).
Et udspændende træ vil indeholde samtlige N punkter og der vil være præcis N-1 kanter i det.
Prøv at tegne et antal punkter og forbind dem med sammenhængende kanter således at der ikke er nogle kredse. Du vil se at der altid er een kant færre end antallet af punkter.
Når algoritmen trin 4 kræver, at der skal udvælges kanter fra grafen efter kriteriet i trin 3 indtil der er valgt N-1 kanter, er det således fordi det søgte træ skal have netop N-1 kanter. Trin 4 er blot stopkriteriet for algoritmen.
"Og denne vægtsummen, hvis jeg har forstået det korrekt, så er det altså summen af værdierne for alle de kanter, som G indeholder? og i mit tilfælde vil det så være antal km, da det er afstanden mellem byer jeg skal finde?"
Korrekt.
Termen 'vægt' er blot en almen betegnelse for den værdi, man knytter til en kant. I dette tilfælde er det helt korrekt en afstand.
Med 'vægtsum' menes summen af vægtene af de kanter, der danner en graf. Bemærk specielt at der kan være mere end eet udspændende træ til en graf. Beregnes vægtsummen for alle sådanne udspændende træer vil den mindste vægtsum repræsentere vægtsummen i det minimale træ. Termen 'minimal' betyder nemlig at der ikke findes udspændende træer, der har en lavere vægtsum.
Svar #15
14. december 2005 af Triangle (Slettet)
Jeg suger til mig. Jeg er ikke længere i tvivl om betydningen af n-1 kanter.
Jeg har netop "beregnet" afstanden mellem de givne byer og har i første omgang tegnet en graf G som indeholder alle mine byer(punkter), og grafen G indeholder således også lukkede kæder.
Da min opgave går ud på at konstruere et minimalt træ for disse byer har jeg vha af algoritmen konstrueret en minimalt træ. Hertil har jeg et spørgsmål, som knytter sig lidt til det sidste afsnit i #14; hvordan kan jeg kontrollere, at har fundet alle udspændende træer?
På forhånd tak
Svar #16
14. december 2005 af fixer (Slettet)
Omformulering af punkt (2):
2) Idet grafen har n punkter vil træet få n-1 kanter, hvilket sikres af algoritmens trin 4. Ifølge sætningen ovenfor er træet derfor et sammenhængde træ med n-1 kanter (P=K+1 <=> K=P-1). Da træet således indeholder alle grafens n punkter er det et udspændende træ.
Svar #17
14. december 2005 af fixer (Slettet)
Det er ikke nødvendigt at finde alle udspændende træer. Algoritmen vil producere eet minimalt træ og det er tilstrækkeligt.
Årsagen til at jeg i #14 nævnte at der kan være mere end eet udspændende træ var blot for at kundgøre betydningen af termen 'minimalt træ' som værende et udspændende træ med mindst mulig vægtsum.
Svar #18
14. december 2005 af Triangle (Slettet)
På forhånd tak.
Henrik
Svar #19
15. december 2005 af Triangle (Slettet)
Hvad menes der med males?
Svar #20
15. december 2005 af fixer (Slettet)
At punktet "males" er derfor sikkert blot et synonym for, at det markeres. Når proceduren terminerer vil de markerede punkter være sådanne, gennem hvilke der findes en frugtbar vej.
Men frugtbar vej menes en vej der der tillader en større strøm gennem netværket.