Grafteori
Hur löser man följande uppgift?
jag vet att grafen med valenserna (1,2,2,2,2,4) inte existerar då summan är ett udda tal (1+2+2+2+2+4=13).
Hur löser man de andra två?
Har du försökt konstruera dem?
Jag har försökt men lyckas ej, det blir alldeles för rörigt. Jag vet inte hur man ska tänka när man ska konstruera grafer
Jag tror att det inte går, men jag ser inget bra sätt att bevisa det.
Ett tips är att en nod har grad 5 i både fall 1 och 3. Så där har du ju bara ett val, ta bort den noden och gör en graf med de resterande 5 noderna (med uppdaterade grader). Då blev det lättare tycker jag.
(annars finns det en generell algoritm, googla på "construct graph with given degree sequence" så ser du den)
nigus skrev:Ett tips är att en nod har grad 5 i både fall 1 och 3. Så där har du ju bara ett val, ta bort den noden och gör en graf med de resterande 5 noderna (med uppdaterade grader). Då blev det lättare tycker jag.
(annars finns det en generell algoritm, googla på "construct graph with given degree sequence" så ser du den)
hur menar du att jag ska ta bort noden 5. Blir fall 1 då (1,2,3,3,3)?
dsvdv skrev:nigus skrev:Ett tips är att en nod har grad 5 i både fall 1 och 3. Så där har du ju bara ett val, ta bort den noden och gör en graf med de resterande 5 noderna (med uppdaterade grader). Då blev det lättare tycker jag.
(annars finns det en generell algoritm, googla på "construct graph with given degree sequence" så ser du den)
hur menar du att jag ska ta bort noden 5. Blir fall 1 då (1,2,3,3,3)?
exakt, ser du något sätt att fortsätta?
nej :/
blir det (0,2,2,3,3)
dsvdv skrev:blir det (0,2,2,3,3)
japp, ser bra ut. Hur ser hela grafen ut?
menar du då grafen (2,3,4,4,4,5)?
hur kommer hela grafen att se ut?
dsvdv skrev:hur kommer hela grafen att se ut?
Du hittade ju grafen för (0,2,2,3,3). Jag antar att du fick fram (0,2,2,3,3) genom att ta (1,2,3,3,3) och koppla ihop första och tredje noden? Så lägg tillbaka den kanten, och den sjätte noden + dess 5 kanter
nigus skrev:dsvdv skrev:hur kommer hela grafen att se ut?
Du hittade ju grafen för (0,2,2,3,3). Jag antar att du fick fram (0,2,2,3,3) genom att ta (1,2,3,3,3) och koppla ihop första och tredje noden? Så lägg tillbaka den kanten, och den sjätte noden + dess 5 kanter
Jag förstår inte.. skulle du kunna rita grafen
dsvdv skrev:nigus skrev:dsvdv skrev:hur kommer hela grafen att se ut?
Du hittade ju grafen för (0,2,2,3,3). Jag antar att du fick fram (0,2,2,3,3) genom att ta (1,2,3,3,3) och koppla ihop första och tredje noden? Så lägg tillbaka den kanten, och den sjätte noden + dess 5 kanter
Jag förstår inte.. skulle du kunna rita grafen
Först hade vi (2,3,4,4,4,5).
Sedan tog vi bort noden med grad 5 och dess kanter, och fick då (1,2,3,3,3).
Sedan drog du en kant mellan ettan och en av treorna och fick (0,2,2,3,3) (eller jag trodde att du gjorde det men jag kanske läste för mycket mellan raderna)
Sedan hittade du en graf som motsvarar (0,2,2,3,3). Nu behöver vi bara lägga tillbaka de kanter/noder som tagits bort för att få en lösning till (2,3,4,4,4,5)
okejjj nu förstår jag tack!
Ni har behandlat fall 1) och 2) men fall 3) finns inte heller någon lösning till. Vi har (1,2,2,4,4,5). Den högsta valensen är 5 vilket betyder att den noden är granne med alla de övriga. Vi har också en ensam stackare som alltså måste vara granne med den nod som har 5 valenser. Om vi nu tar bort dessa två har vi kvar (1,1,3,3). De nya ensamma noderna kan vi också ta bort och vi får kvar (2,2). Men en nod i en graf med bara två noder kan inte ha valens 2, utan bara 1. (Kemister med sina dubbelbindningar gjöre sig icke besvär i detta sammanhang!) Alltså sluter vi oss till att fall 3) ej går att konstruera.
Fall 2 löser man enklast genom att se att summan av valenserna är udda.
