Citat:
Två små frågor om grafteori. Hur ska jag tänka här?
* I ett land finns det bara enkelriktade vägar, men det är möjligt att åka mellan godtyckliga två städer och som mest passera en annan stad. En av vägarna stängdes för reparation, men det är fortfarande möjligt att åka mellan godtyckliga två städer. Visa att det kan göras genom att passera som mest två andra städer.
* I ett land finns det bara enkelriktade vägar, men det är möjligt att åka mellan godtyckliga två städer och som mest passera en annan stad. En av vägarna stängdes för reparation, men det är fortfarande möjligt att åka mellan godtyckliga två städer. Visa att det kan göras genom att passera som mest två andra städer.
Det framgår att det i startläget går att åka från valfri stad till valfri stad i max två steg. Sedan stängs en enda väg av, men det går fortfarande att ta sig från valfri stad till valfri stad.
Säg att den avstängda vägen gick från stad A till stad B (i ett steg alltså - vi kallar den avstängda vägens startstad för A och den avstängda vägens slutstad för B). Det måste gå minst en ytterligare väg från A och komma minst en ytterligare väg till B för att det fortfarande ska kunna gå att ta sig från valfri stad till valfri stad.
Det finns nu två huvudsakliga fall att beakta för vägar mellan två godtyckliga städer:
- De vägar som tidigare gick via A → B
- De vägar som inte tidigare gick via A → B
Vägarna i fall 2 är opåverkade och går således fortfarande via max en annan stad. Vägarna i fall 1 har antingen A som startstad eller B som slutstad, eftersom samtliga vägar tidigare gick via max en annan stad.
Vägar med A som startstad kan nu gå från A till en annan stad X (det finns ju minst en som fortfarande kan nås direkt från A) och därifrån gå vidare till slutstaden. Vägen från X till slutstaden kan inte gå via A → B eftersom den vägen inte är öppen, men samtidigt finns vägen enligt uppgiften. Den är alltså en väg som i fall 2 ovan och går alltså via max en annan stad.
Vägar med B som slutstad kan gå via en stad Y från vilken det går en direkt väg till B (det finns ju minst en sådan). Vägen från startstaden till Y kan inte gå via A → B eftersom den inte är öppen. Eftersom det ändå ska finnas en väg från startstaden till Y så måste den vägen också vara som i fall 2 och alltså gå via max en annan stad.
Således går alla vägar mellan alla par av städer via max en annan stad (fall 2) alternativt via två andra städer (fall 1).
Citat:
Har du inte skrivit fel i villkoret? Om 2 > m > n och både m och n är heltal så kan man antingen ha m = 1 och n = 0 eller så måste minst en av dem vara negativ. Inget av detta motsvarar definitionen av kompletta bipartita grafer.
Kanske ska det egentligen vara 2 < m < n? I så fall så är det en fråga om att man ska gå via olika kanter och noder och så småningom komma tillbaka till samma nod. Eftersom grafen är komplett bipartit så kan alla noder i endera partitionen gå direkt till samtliga noder i den andra partitionen.
Den partition som har det mindre antalet noder är alltså begränsande, och eftersom man måste gå till en ny nod i varje steg så blir det totala antalet noder (och kanter) i kretsen 2 gånger det mindre antalet noder. Om villkoret egentligen är 2 < m < n så blir alltså svaret 2m.