Graf- och kombinatorikuppgift
Hejsan! Har försökt lösa denna uppgift men har gått åt helt åt skogen, nu vet jag inte ens hur jag ska börja så om någon skulle kunna hjälpa mig hade det verkligen uppskattats, här kommer den:
Låt talen {1, 2, ..., 15} utgöra hörn i en graf G och låt talparet (a, b) vara en kant omm SGD(a, b)>1. Hur många komponenter har G? Bestäm den längsta stigen utan upprepade hörn i G.
Välkommen till Pluggakuten! Hur har du börjat? Vilka talpar uppfyller kravet om att SGD(a,b) > 1? :)
Tack! Har tagit bort allt jag har gjort så har inte riktigt börjat för jag förstår inte vad jag ska göra med informationen i frågan. Alla jämna talpar uppfyller at SGD(a,b)>1 om jag inte är ute och cyklar
Ta uppgiften i flera steg, så blir det lättare.
Alla jämna talpar uppfyller at SGD(a,b)>1 om jag inte är ute och cyklar
Det stämmer, men hur är det med övriga tal? 3 och 7? 12 och 15?
Ja precis, alla de har samtliga SGD(a,b)>1. Jag har tolkat uppgiften som att det endast finns EN sådan kant i hela grafen men jag antar att det finns en kant mellan varje hörn som har SGD(a,b)>1, eller är jag rätt ute då?
polisen112 skrev:Ja precis, alla de har samtliga SGD(a,b)>1.
Nja, alla talpar uppfyller inte det. SGD(3,7) = 1, exempelvis.
Jag har tolkat uppgiften som att det endast finns EN sådan kant i hela grafen men jag antar att det finns en kant mellan varje hörn som har SGD(a,b)>1, eller är jag rätt ute då?
Ja, om hörnen a och b uppfyller att SGD(a,b) > 1 kommer det att finnas en kant mellan a och b. Det kommer därför att finnas en kant mellan hörn 12 och 15, men ingen kant mellan hörn 3 och 7.
Ja precis, menade inte att 3 och 7 har en SGD(a,b)>1 utan det kom bara ut fel.
Nu förstår jag hur jag tänkt fel hade bara fått någon låsning i skallen, nu ska detta lösa sig, stort tack!
Sådant händer, vad bra att knuten kunde redas ut. Varmt välkommen tillbaka till tråden om du kör fast senare i uppgiften! :)
