Grafer; visa att alla träd med minst två noder har minst två noder med gradtal ett
Frågan är i rubriken.
Jag började med att skriva upp det vi vet om ett träd:
N = antal noderK = antal kanterG = totalt antal gradtal för trädet
K = N - 1G = 2 * K = 2 * (N - 1) = 2 * N - 2
Jag förstår att det kommer att bli så, då det alltid kommer att finnas minst två ändar av ett träd, men jag vet inte riktigt hur jag fortsätter med ett bevis. Har någon något förslag på hur jag kan tänka för att komma vidare?
Tack!
Jag har inget bevis, men tror att nyckeln är att ett träd inte har cykler. Så jag skulle börja med att anta att trädet bara har en enda nod med gradtal ett. Sedan skulle jag försöka visa att det i så fall måste finnas en cykel, dvs motsägelse.
Kontradiktion:
Om det inte finns några noder med gradtal ett. Då är G >= 2N, eller hur? Eller >= 2N-1 om bara en nod med gradtal ett.
Men! G=2N-2, så ...
Som Marilyn påpekade gjorde jag en felaktig definition. Jag skrev hur dessa förhållanden är då det är en sammanhållen graf vilket det ju inte är...
En nod kan ju ha 1, 2, 3, ... gradtal, beror ju endast på hur trädet är uppbyggt. Jag kommer inte framåt i detta, jag har kollat in lösningsförslaget, och jag har lite svårt att fatta det. Kanske ni kan få hjälp att hjälpa mig av den?
Visa spoiler
OK. Det här är inte min starka sida, men tror ändå mitt bevis av att motsatsen inte håller är OK. Det borde leda till att: 2N-2 >= 2N-1, vilket inte kan vara sant. QED?
Om jag förstått ditt resonemang rätt;
Gradtalen för en sammansatt graf är G >= 2N.
Om vi nu tar bort 1 nod, N - 1, betyder det att G >= 2(N-1) = 2N - 2.
Jag ser dock inte riktigt vad detta skulle bevisa, eller hur man skulle kunna leda detta till beviset.
Vi låter vara en nod med gradtal 1.
Gradtalet för ett 2-nodigt träd är då 2, .
Ett träd får inte vara sammansatt. Om vi kopplar på den nya noden till så kommer att få gradtal 2, medans den nya noden kommer att bli betecknad då den endast kommer att ha gradtal 2. Denna process repeteras för ett träd, och då ett träd inte innehåller cyklar så kommer det endast att kunna bli fler noder som endast kopplas ihop med trädet men som ej får ett löv.
Skulle detta kunna fungera som något slags bevis, eller förståelse för problemet?
Utnyttja kretsfriheten. Mer precis: i en kretsfri graf finns en längsta vandring. Vilket gradtal har begynnelse- och slutnod i en vadring av maximal längd?
”Utnyttja kretsfriheten. Mer precis: i en kretsfri graf finns en längsta vandring. Vilket gradtal har begynnelse- och slutnod i en vadring av maximal längd?”
Jaaa! Smart.
Ja jag håller med, tydligt resonemang!
