Matematik
Grafer - korrekt bevis?
19. december 2005 af
Triangle (Slettet)
Godaften..
Jeg sidder med en sætning der vedrører afstanden fra et punkt v til ethvert andet punkt i en turnering. Sætningen lyder på at denne afstand vil være 1 eller 2.
Jeg har vist sætningen ved følgende, men er lidt i tvivl om det er fyldestgørende nok (korrekt):
Vi antager, at vi har punkterne u og v, samt at der for u gælder ugr(u) = max., dvs. u har et maksimalt antal udgrad. Vi antager yderligere, at modsætningen d(u,v) 3 gælder for førnævnte antagelse. Vi vil nu se, at der fra v er buer til alle u’s naboer samt til u. Vi opnår hermed en modstrid ved at se at v’s udgrad overstiger u's.
Jeg sidder med en sætning der vedrører afstanden fra et punkt v til ethvert andet punkt i en turnering. Sætningen lyder på at denne afstand vil være 1 eller 2.
Jeg har vist sætningen ved følgende, men er lidt i tvivl om det er fyldestgørende nok (korrekt):
Vi antager, at vi har punkterne u og v, samt at der for u gælder ugr(u) = max., dvs. u har et maksimalt antal udgrad. Vi antager yderligere, at modsætningen d(u,v) 3 gælder for førnævnte antagelse. Vi vil nu se, at der fra v er buer til alle u’s naboer samt til u. Vi opnår hermed en modstrid ved at se at v’s udgrad overstiger u's.
Svar #2
20. december 2005 af fixer (Slettet)
Denne sætning kan umuligt være korrekt. Der må være tale om begrebsforvirring, eller at du tilbageholder væsentlig information.
En turnering er en orienteret, komplet graf. Der er ingen garanti for at der eksisterer en vej imellem to arbitrære punkter. Gør der ikke det, er afstanden imellem disse punkter definitionsmæssigt uendelig.
Derudover er der _ingen_ restriktioner på længden af en kant. Kantlængden er blot en numerisk værdi knyttet til kanten. Hvis sætningen skulle have en chance for at være korrekt - hvad den altså ikke har - ville det kræve en underliggende forudsætning om, at alle kantlængder er 1.
Hvis der ikke menes turnering, men istedet blot en komplet graf, er sætningen heller ikke rigtig. I en sådan ikke-orienteret komplet graf er der altid en vej mellem arbitrære punkter, thi alle punkter er forbundne med hinanden. Afstanden mellem to arbitrære punkter p og q er da blot længden af kanten mellem p og q. Men også her gælder at denne kant kan være tildelt en vilkårlig numerisk værdi repræsenterende dens længde.
En turnering er en orienteret, komplet graf. Der er ingen garanti for at der eksisterer en vej imellem to arbitrære punkter. Gør der ikke det, er afstanden imellem disse punkter definitionsmæssigt uendelig.
Derudover er der _ingen_ restriktioner på længden af en kant. Kantlængden er blot en numerisk værdi knyttet til kanten. Hvis sætningen skulle have en chance for at være korrekt - hvad den altså ikke har - ville det kræve en underliggende forudsætning om, at alle kantlængder er 1.
Hvis der ikke menes turnering, men istedet blot en komplet graf, er sætningen heller ikke rigtig. I en sådan ikke-orienteret komplet graf er der altid en vej mellem arbitrære punkter, thi alle punkter er forbundne med hinanden. Afstanden mellem to arbitrære punkter p og q er da blot længden af kanten mellem p og q. Men også her gælder at denne kant kan være tildelt en vilkårlig numerisk værdi repræsenterende dens længde.
Skriv et svar til: Grafer - korrekt bevis?
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.