Grafteori¶
En graf är det enklaste intressanta matematiska objektet: en mängd hörn (punkter) förbundna med kanter (linjer). Det är allt. Trots den skala uppställningen följer förvånansvärt mycket struktur, och den modellerar allt från vägnät till molekyler till schemaläggning.
Vi skriver \(v = \lvert V \rvert\) för antalet hörn och \(e = \lvert E \rvert\) för antalet kanter. De examinerbara resultaten är få och de flesta har enradsbevis — men de är nästan alla formulerade som "om och endast om", och poängen kommer från att hantera båda riktningarna (eller citera rätt en). Fortsätt fråga dig: vilken riktning behöver jag här?
Grader¶
Graden \(\deg(x)\) av ett hörn är hur många kantändar som möts vid det — löst, hur många linjer som kommer ut ur den punkten.
Handskakningslemmat
Summan av alla grader är alltid jämn — faktiskt exakt två gånger antalet kanter.
Varför. Varje kant har två ändar, och varje ände bidrar med \(1\) till graden av något hörn. Så varje kant lägger exakt \(2\) till gradsummans totalsumma. (Namnet kommer från: på en fest är totala antalet handskakningsändar två gånger antalet handskakningar.)
Draget det låser upp: antalet hörn av udda grad måste vara jämnt. Så en fråga som "finns det en graf med graderna \(3,3,3,3,3\)?" avgörs direkt — det är fem udda grader som summerar till \(15\), ett udda tal, omöjligt.
Eulerkretsar och eulervägar¶
Uppkallade efter problemet som startade hela ämnet (broarna i Königsberg). En eulerkrets är en vandring som använder varje kant exakt en gång och slutar där den började.
Eulers sats
En sammanhängande graf har en eulerkrets om och endast om varje hörn har jämn grad.
Den har en eulerväg (varje kant en gång, men tillåten att sluta någon annanstans) om och endast om den har exakt noll eller två hörn av udda grad. Om det finns två måste vägen börja i det ena och sluta i det andra.
Varför jämn grad är det magiska villkoret. Föreställ dig vandringen passera genom ett hörn: den kommer in längs en kant och lämnar längs en annan, och använder kanter i in–ut-par. För att vandringen ska förbruka alla kanter vid ett hörn och ändå kunna lämna varje gång, måste de kanterna paras ihop perfekt — dvs. graden måste vara jämn. Ett hörn av udda grad har en kant kvar oparad, så vandringen kan bara stanna där — vilket är varför hörn av udda grad är precis de tillåtna ändpunkterna för en väg, och helt förbjudna i en krets.
Tentamen (maj 2024, uppgift 2d)
"Har grafen en eulerkrets?"
Ett fullständigt svar är två meningar: En sammanhängande graf har en eulerkrets om och endast om varje hörn har jämn grad. Här har varje hörn udda grad, så den har ingen. Ange kriteriet, kontrollera det mot denna graf, dra slutsatsen. Det är hela poängen — inget vinns på att göra mer, och poäng förloras på att göra mindre (t.ex. att hoppa över kriteriet).
Hamiltoncykler¶
Bedrägligt likt namn, vilt annorlunda svårighet. En hamiltoncykel besöker varje hörn exakt en gång och återvänder till starten.
Kontrasten mot euler är det man ska bränna in i minnet:
| Besöker… | Hur svårt att testa | |
|---|---|---|
| Euler | varje kant en gång | Lätt — kontrollera bara graderna |
| Hamilton | varje hörn en gång | Svårt — inget känt effektivt kriterium alls |
Det finns inget prydligt "om och endast om" för hamiltonicitet. Så de två riktningarna kräver olika sorters svar:
- För att visa att en finns: bara skriv ner den. En hörnföljd som \(a_0 a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_0\) är ett fullständigt bevis — läsaren kan verifiera den för ögat, så inget ytterligare argument behövs.
- För att visa att ingen finns: du behöver ett strukturellt skäl. Den vanliga hävstången är bipartiethet (nedan): en hamiltoncykel i en bipartit graf måste studsa fram och tillbaka mellan de två sidorna, så den kräver att sidorna är lika stora. Om de inte är det kan ingen hamiltoncykel finnas.
Bipartita grafer¶
En graf är bipartit om du kan dela hörnen i två grupper så att varje kant går mellan grupperna — ingen stannar inom en grupp. Tänk två lag, där spelare bara någonsin länkar till motståndarlaget. Ekvivalent är det en graf du kan 2-färga utan att någon kant förbinder likfärgade hörn.
Bipartietskriterium
En graf är bipartit om och endast om den inte har någon cykel av udda längd.
Intuition för kriteriet. Om du 2-färgar genom att alternera längs kanter (röd, blå, röd, blå, …), tar en cykel dig tillbaka till din start — och du återvänder till samma färg bara om cykeln hade jämn längd. En udda cykel skulle tvinga ett hörn att vara båda färger, vilket är motsägelsen.
- För att bevisa att en graf är bipartit: uppvisa 2-färgningen (namnge de två grupperna).
- För att bevisa att den inte är det: uppvisa en enda udda cykel — en triangel är den minsta och oftast lättaste.
Isomorfi¶
Två grafer är isomorfa om de är samma graf ritad annorlunda — formellt, en ommärkning av hörn (en bijektion) som förvandlar den ena grafens kanter exakt till den andras.
- För att bevisa isomorfi: ange hörnmotsvarigheten explicit, och kontrollera att varje kant på ena sidan avbildas på en kant på den andra.
-
För att bevisa icke-isomorfi: hitta en egenskap som överlever ommärkning (en invariant) men skiljer sig mellan de två. Billiga invarianter att pröva, ungefär lättast först:
- Antal hörn; antal kanter.
- Gradsekvensen — den sorterade listan av alla hörngrader.
- Antal cykler av varje längd; midjevidden (kortaste cykeln).
- Sammanhang; antal sammanhängande komponenter.
- Bipartit eller inte.
Om någon av dessa skiljer sig kan graferna inte vara isomorfa — klart.
Matchande gradsekvenser bevisar ingenting på egen hand
Lika gradsekvenser är nödvändigt men inte tillräckligt: det finns gott om par av icke-isomorfa grafer med identiska gradsekvenser. Så om gradsekvenserna stämmer har du uteslutit ingenting — du måste antingen gräva fram en finare invariant eller faktiskt konstruera ommärkningen. Deklarera inte två grafer isomorfa bara för att deras gradsekvenser överensstämmer.
Träd¶
Ett träd är en sammanhängande graf med inga cykler — "ingen redundans"-grafen, där det finns precis ett sätt att ta sig mellan två hörn.
Kantantal i träd
Varje träd uppfyller \(v = e + 1\) — ett hörn mer än kanter.
Varför. Börja från ett enda hörn (0 kanter) och låt trädet växa genom att lägga till ett hörn i taget; varje nytt hörn måste fästas med exakt en ny kant (fler skulle skapa en cykel, färre skulle koppla bort det). Så kanter släpar alltid efter hörn med ett.
Dessa karakteriseringar är alla ekvivalenta — vilken som helst kan vara definitionen, och olika problem vill ha olika: sammanhängande och cykelfri; sammanhängande med \(v = e+1\); cykelfri med \(v = e+1\); precis en väg mellan två hörn.
Ett uppspännande träd till en graf \(G\) är en delgraf som (a) är ett träd och (b) innehåller alla \(G\):s hörn — ett minimalt skelett som ändå förbinder allt. Varje sammanhängande graf har ett: radera upprepade gånger en kant som ligger på en cykel; att radera en cykelkant kopplar aldrig bort grafen, och du stannar när inga cykler återstår — ett träd.
Planära grafer¶
En graf är planär om den kan ritas i planet med inga korsande kanter. Betoning på kan: planaritet handlar om huruvida någon korsningsfri ritning finns. En stökig ritning full av korsningar bevisar inte att en graf är icke-planär — det kan bara vara en dålig ritning av en fullkomligt planär graf.
Eulers formel
För en sammanhängande planär graf ritad utan korsningar,
där \(f\) är antalet ytor — regionerna som ritningen delar planet i, inklusive den enda obegränsade regionen på utsidan.
Det enda folk glömmer: räkna den yttre ytan. En triangel ritad i planet har \(f = 2\), inte \(1\) — insidan och utsidan.
Tentamen (maj 2024, uppgift 2a–c): grafen med 8 hörn
(a) "Gör en planär ritning." Den officiella lösningen är bokstavligen en mening — flytta bara två av de parallella innerkanterna till utsidan — en bra påminnelse om att svaret på en planaritetsfråga är en omritning, inte en uträkning. Du ombeds hitta den korsningsfria bilden.
(b) "Kontrollera Eulers formel." Från din omritning: \(v = 8\), \(e = 8 + 4 = 12\), och genom att räkna regioner (glöm inte utsidan) \(f = 6\):
Räkna \(f\) från din egen ritning — Eulers formel kontrollerar den specifika ritningen.
(c) "Har den en hamiltoncykel?" Ja: \(a_0 a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_0\). Att skriva ner cykeln är hela beviset (se Hamiltoncykler).
Följder värda att kunna¶
Eulers formel har två följdsatser som ger snabba icke-planaritetsbevis. För en sammanhängande enkel planär graf med \(v \geq 3\):
Hur man använder dem: om en graf har för många kanter för sitt hörnantal kan den inte vara planär.
- \(K_5\) (5 hörn, alla förbundna): \(v = 5\), \(e = 10\). Men \(3v - 6 = 9 < 10\). Så \(K_5\) är inte planär.
- \(K_{3,3}\) (två grupper om 3, alla korskanter): bipartit, så använd den andra gränsen. \(v = 6\), \(e = 9\), men \(2v - 4 = 8 < 9\). Inte planär.
Dessa två grafer, \(K_5\) och \(K_{3,3}\), är de fundamentala hindren: Kuratowskis sats säger att en graf är planär precis när den inte innehåller någon delgraf som är en delning av någondera. Varje icke-planär graf gömmer en av dessa två inuti sig.