Side 3 - Att: Epsilon, Dominik Hazek, Duffy. - Matematik

Svar #41
16. december 2005 af Triangle (Slettet)

Fantastisk!

Jeg er med i induktionsbeviset lige indtil det sidste : ½(n+1)n = P(n+1)
hvorfor gælder dette? Er det fordi at antallet af punkter i enhver graf G er det dobbelte af antallet af kanter?

Brugbart svar (0)

Svar #42
16. december 2005 af fixer (Slettet)

Nej, men bemærk at ved indsættelse af n+1 i udtrykket for P(n) fås

P(n+1) = ½(n+1)n

hvilket præcist er lig det antal kanter, ½(n+1)n, vi har beregnet, der er i en fuldstændig G(n+1) graf.

Altså: Hvis det er sandt, at antallet af kanter i en fuldstændig G(n)-graf er P(n) så er antallet af kanter i en fuldstændig G(n+1)-graf P(n+1).

Vi ved P(2) er sand. Vi har netop vist at så er P(3) også sand. Men dermed

P(3) => P(4)
P(4) => P(5)
P(5) => P(6)
:
P(n) => P(n+1)

og derfor er P(n+1) sand for alle n>=2. Det er det, der er hele grundtanken i induktionsbeviset.

Brugbart svar (0)

Svar #43
16. december 2005 af fixer (Slettet)

Korrektion:

"og derfor er P(n+1) sand for alle n>=2."

skal være:

og derfor er P(n) sand for alle n>=2.

Svar #44
16. december 2005 af Triangle (Slettet)

Det nytter altid at fatte blyanten og et stykke papir. Jeg er med nu. Tak
Må jeg tillade mig at stille yderligere spørgsmål om emnet, hvis (når) det er tilfældet?

Brugbart svar (0)

Svar #45
16. december 2005 af fixer (Slettet)

Naturligvis.

Svar #46
16. december 2005 af Triangle (Slettet)

Hej igen fixer.

Jeg har nu læst en del om "firfarveproblemet", som man arbejder med vha. diskret matematik. Jeg har læst noget historisk såvel som matematisk. Man har gennem det sidste århundrede påstået at have løst problemet, og er siden hen blevet erklæret for falske. I 1976 blev det officielt erklæret af Haken og Appel at alle lande kan firfarves. Mange af de ting jeg har læst om problemet tager udgangspunkt i læren om træer. Men hvordan er det man anvender dette men henblik på at løse "problemet"

Svar #47
18. december 2005 af Triangle (Slettet)

Jeg har et spørgsmål.
I en eulergraf har man en lukket kæde(kreds) hvor man passerer alle grafens kanter præcis en gang..
I en hamiltongraf har man en lukket kæde, hvor man passerer alle grafens punkter præcis en gang..

Kan man forestille sig at alle eulergrafer også kan være en hamiltongraf? og hvorfor?

Svar #48
18. december 2005 af Triangle (Slettet)

Jeg er lidt i tvivl om "problemet" i #46 er et konkret problem som løses vha grafteorien, eller om det er en hel gren for sig?

Henrik

Brugbart svar (0)

Svar #49
18. december 2005 af fixer (Slettet)

#46
Ved en k-farvning af en graf G forstås en afbildning af mængden, P(G), af punkter i G ind i en mængde med k elementer, kaldet "farver" således, at når to punkter er forbundet med en kant, da har de forskellig farve.

Dersom nu hvert land repræsenteres med et punkt, og nabolandes punkter forbindes med kanter, da fremkommer netop en graf og man kan spørge sig hvorvidt denne graf kan k-farves, specielt 4-farves.

#47
Det gælder ikke at en Eulertur også er en Hailtontur. Bemærk nemlig at i en Eulretur kan hvert punkt besøges mere end een gang og i en Hamiltontur er det ikke nødvendigt at besøge hver kant.

Svar #50
18. december 2005 af Triangle (Slettet)

så man kan altså farve ethvert landkort med 4 farver, så der ikke er to lande med samme farve der støder op til hinanden? Lidt utroligt, hvordan kan dette lade sig gøre?

Brugbart svar (0)

Svar #51
18. december 2005 af fixer (Slettet)

#50
Forstår ikke spørgsmålet. Hvis det er bevist ladesiggørligt, så er det jo således.

Svar #52
18. december 2005 af Triangle (Slettet)

Altså jeg er i tvivl om man kan farve ethvert landkort med netop 4 farver, således at der ikke er to lande (punkter) med samme farve der støder op til hinanden. Ved ikke om dette er lidt tydeligere?

Hvad mener du med det sidste?

Brugbart svar (0)

Svar #53
18. december 2005 af fixer (Slettet)

I #46 påstås at den graf, der fremkommer ved metoden nævnt i #49 anvendt på alle lande, bevisligt kan 4-farves. Så er den vel ikke længere.

Svar #54
18. december 2005 af Triangle (Slettet)

når man så skal forklare hvorledes grafteorien anvendes til at løse problemet, så skal man vel forklare at de begreber og definitioner der gør sig gældende i løsningen af problemet er elementer af graftoeri, og selvfølgelig uddybe problemet? Man kan jo vel ikke løse "problemet", men måske løse opgave der knytter sig til emnet, eller er dette misforstået?

Svar #55
18. december 2005 af Triangle (Slettet)

Hvad er duale grafer?

Brugbart svar (0)

Svar #56
19. december 2005 af fixer (Slettet)

Det kræver en længere forklaring for at være fyldestgørende, idet begrebet 'plan graf' først må defineres.

Det er nok på tide at oprette en ny tråd til dette og efterfølgende nye spørgsmål. Jeg skal nok finde dem og svare.

Matematik

Side 3 - Att: Epsilon, Dominik Hazek, Duffy.

Skriv et svar til: Att: Epsilon, Dominik Hazek, Duffy.