Uppsatser i kurs SF1631,
Diskret matematik för D3

Vad ska uppsatsen innehålla?

Du ska läsa in ett område och presentera det i en uppsats på 2000 till 3000 ord skriven i Word eller TEX. För att ha något att bygga upp uppsatsen kring ska du själv formulera ett problem i vardagliga termer, modellera det matematiskt och lösa det med hjälp av den matematik du har läst in. Du gör själv disposition av din uppsats, men det krävs att den inleds med en introduktion där problemet formuleras och (åtminstone en antydan om) svaret ges, samt att den avslutas med en slutsats där du kort sammanfattar vad du har sagt och förtydligar samspelet mellan den studerade matematiken och det aktuella problemet. Däremellan ska du på ett så klart och enkelt, trevligt och läsvärt sätt som möjligt modellera problemet matematiskt, presentera den matematik du behöver för att lösa problemet och sedan presentera lösningen.

Förslag till uppsatsämnen

Tretton förslag till uppsatsämnen ges nedan. Kom ihåg att ni gärna får skriva på engelska istället för på svenska om ni hellre vill öva på det! Kraven på stil och språklig korrekthet blir då något lägre men övriga krav (på förståelighet, disposition, originalitet, matematisk korrekthet etc.) är naturligtvis oförändrade. Vidare är ni välkomna att föreslå egna områden för uppsatser men de måste godkännas av föreläsaren i förväg. Säg till föreläsaren om ni har svårt att hitta litteratur. Det är ofta värt att söka på nätet.

Planaritet och Kuratowskis sats

 Vissa grafer kan omöjligt ritas på ett papper utan korsande kanter. De grafer som kan ritas utan korsande kanter kallas planära. Planaritetsbegreppet är av stor praktisk betydelse. Kuratowski bevisade ett mycket djupt resultat: att en graf är planär om och endast om den inte har någon delgraf som "ser ut som" (är homeomorf med) någon av graferna K5 eller K3,3. Det finns moderna effektiva algoritmer för att avgöra om en graf är planär och för att verkligen rita planära grafer utan korsande kanter. Om man får rita grafen på ytan av en torus istället för på ett plant papper blir några fler grafer ritbara och andra grafer spelar den roll som Kuratowskis grafer gör i det planära fallet.

Litteraturförslag: "Graphs, Colourings and the Four-colour Theorem", kap 7, av Robert A. Wilson, "Introduction to Graph Theory", kap 5, av Robin J. Wilson, "Algorithmic Graph Theory", kap 3, av Alan Gibbons. WWW: Sök på "planar graphs".

Eulervägar och eulerkretsar

En eulerväg i en graf är en väg som besöker alla kanter exakt en gång. En graf har alltså en eulerväg om man kan rita den i en rörelse utan att någonsin lyfta pennan från papperet. Om vägen börjar och slutar i samma hörn kallas det en eulerkrets. Euler fann en mycket elegant karakterisering av de grafer som har eulerkretsar: de är sammanhängande och alla hörn har jämn valens. Det finns motsvarande satser även för riktade grafer, liksom effektiva algoritmer för att finna eulervägar/-kretsar. Om grafen inte är eulersk (dvs inte har någon eulerkrets) kan man fråga sig vilken den kortaste väg är som besöker alla kanter minst en gång. Det problemet kallas "kinesiska brevbärarproblemet".

Litteraturförslag: "Introduction to Graph Theory", kap 3.6, av Robin J. Wilson, "Algorithmic Graph Theory", kap 6.1-2, av Alan Gibbons. WWW: Sök på "Eulerian graphs".

Hamiltonstigar och hamiltoncykler

En hamiltonstig i en graf är en stig som besöker alla hörn exakt en gång. Om stigen börjar och slutar i samma hörn kallas det en hamiltoncykel. Problemet att finna hamiltonstigar är besläktat med det berömda handelsresandeproblemet: att finna den kortaste väg som besöker alla städer på en given karta. Till skillnad från vad gäller eulervägar finns ingen karakterisering av hamiltonska grafer (dvs grafer som har en hamiltoncykel), men många tillräckliga villkor är kända. Problemet att avgöra om en graf är hamiltonsk är NP-komplett, men många approximationsalgoritmer har utarbetats för olika situationer.

Litteraturförslag: "Introduction to Graph Theory", kap 3.7, av Robin J. Wilson, "Algorithmic Graph Theory", kap 6.3, av Alan Gibbons. WWW: Sök på "Hamiltonian graphs" och "traveling salesman problem".

Catalantal och antalet binära träd

En viktig kombinatorisk talföljd börjar 1,2,5,14,42,... Dessa tal kallas catalantal efter matematikern Eugene Catalan och räknar väldigt många kombinatoriska objekt, bland annat de datalogiskt viktiga objekten binära träd och välformade parentesuttryck. Catalantalen uppfyller en ickelinjär rekursion som kan lösas med hjälp av genererande funktioner. Resultatet blir en vacker explicit formel. Fantastiska bijektioner finns mellan de olika objekt som räknas av catalantal.

Litteraturförslag: "Discrete and combinatorial mathematics", kap 10.5, av Ralph Grimaldi. WWW: Sök på "Catalan numbers".

Antalet spännande träd

Cayley fann att antalet spännande träd i den kompletta grafen har en vacker formel: n upphöjt till n-2. Den så kallade matristrädsatsen ger ett enkelt determinantuttryck för antalet spännande träd i en godtycklig graf. Antalet spännande träd kallas ofta för "komplexiteten" hos grafen och är en viktig storhet i vissa algoritmiska problem. För Cayleys formel finns ett slående bijektionsbevis, den så kallade prüferkoden.

Litteraturförslag: "Introduction to Graph Theory", kap 4.10, av Robin J. Wilson, "Algorithmic Graph Theory", kap 2.1, av Alan Gibbons. WWW: Sök på "spanning trees".

Kromatiska polynom

En giltig hörnfärgning av en graf är en färgning av hörnen sådan att grannar har olika färg. Många problem kan översättas till graffärgningsproblem, exempelvis problemet att tilldela radiosändare (hörn) sändingsfrekvenser (färger) så att grannsändare inte sänder på samma frekvens. Givet tillgång till ett visst antal färger är man intresserad av om grafen har en giltig färgning och i så fall hur många. Det kromatiska polynomet för en graf säger hur många giltiga färgningar som grafen har för ett givet antal färger. Polynomet bestäms enklast genom ett rekursivt förfarande som är skojigt att utföra.

Litteraturförslag: "Introduction to Graph Theory", kap 6.21, av Robin J. Wilson, "Graphs, Colourings and the Four-colour Theorem", avsnitt 8.5, av Robert A. Wilson, "Discrete and combinatorial mathematics", kap 11.6, av Ralph Grimaldi. WWW: Sök på "chromatic polynomial".

Fyrfärgssatsen

Fyrfärgssatsen säger att varje planär graf har en giltig hörnfärgning som använder högst fyra färger. Satsen är berömd för att den så länge förblev obevisad och för att den till slut 1976 bevisades med hjälp av en gigantisk datorkörning som kontrollerade det tusental fall till vilka man hade lyckats reducera problemet. Det är ganska enkelt att bevisa att det räcker med sex färger. Det är svårare att bevisa att det räcker med fem färger, men fortfarande förståeligt för en teknolog. Beviset för fyrfärgssatsen behärskar dock ingen (utom möjligtvis datorn) i sin helhet. Eftersom själva problemet är så enkelt att förstå attraherar det många människor, både kompetenta matematiker och amatörer, som inte sällan tror sig ha funnit en lösning. Ett förbättrat bevis, dock fortfarande med datorstöd, kom 1995.

Litteraturförslag: "Graphs, Colourings and the Four-colour Theorem", av Robert A. Wilson, "Introduction to Graph Theory", kap 6.19, av Robin J. Wilson, "Algorithmic Graph Theory", kap 7.3, av Alan Gibbons. WWW: Sök på "four-color theorem".

Matchning i ickebipartit graf

Med hjälp av flödesteori finner man lätt maximala matchningar i bipartita grafer. Men om grafen inte är bipartit är det inte alls lika lätt utan man får då använda mer komplicerade algoritmer med blommor och ungerska träd! Ett exempel på ett matchningsproblem som inte är bipartit är pilotproblemet: Piloter ska samarbeta två och två men alla kan inte samarbeta med alla. Dra en kant mellan varje par av piloter som kan samarbeta med varandra. En maximal matchning i denna graf ger effektivaste utnyttjande av arbetskraften.

Litteraturförslag: "Algorithmic Graph Theory", kap 5.2, av Alan Gibbons, "Algorithmic Graph Theory", kap 8.3, av James McHugh. WWW: Sök på "non-bipartite matching".

Stabil matchning: äktenskap utan pengar emellan

I en by finns ett antal giftasmogna heterosexuella män och kvinnor. Varje man rangordnar alla kvinnor och varje kvinna rangordnar alla män efter hur åtråvärda de är. Nu ska alla gifta sig. Äktenskapen är instabila om det finns en man och en kvinna som båda föredrar varandra framför sina äkta makar, ty då kommer de att överge dem och gifta sig med varandra istället. Kan man alltid åstadkomma stabila äktenskap ? Svaret är ja, och det finns en trevlig algoritm med frierier, förlovningar och giftermål som ger en sådan lösning. Om även homosexualitet ingår i modellen kan det dock finnas situationer där ingen stabil lösning existerar. Mängder av lösta och olösta kombinatoriska och datalogiska problem föreligger inom detta område. Världens store expert på området, Alvin Roth, har en innehållsrik webbsida. Han har upptäckt att algoritmen för stabila äktenskap, som uppfanns av matematiker 1960, redan sedan 1951 används i USA för att matcha ihop läkarstudenter med sjukhus för praktikplats motsvarande svensk AT.

Litteraturförslag: "Two-sided matching" av Alvin Roth och Marilda Sotomayor. WWW: Sök på "stable matching problem".

Stabil matchning: äktenskap med pengar emellan

Samma modell som ovan, men med tillägget att skillnaden i ranking kan mätas i pengar: Alice kanske tycker att Per är attraktivare än Pål men att skillnaden uppvägs om Pål lägger tretusen kronor emellan. I denna modell är alltså resultatet dels en matching av män och kvinnor (eller, oftare inom nationalekonomi, arbetare och arbetsgivare), dels en betalning inom varje äktenskap. Finns det alltid en stabil lösning i denna modell? Javisst! Här kommer linjär algebra in och problemet kan lösas antingen med hjälp av linjär programmering eller med en auktionsprocedur. Världens store expert på området, Alvin Roth, har en innehållsrik webbsida.

Litteraturförslag: "Two-sided matching" av Alvin Roth och Marilda Sotomayor. WWW: Sök på "assignment problem".

Husbytarproblemet

I Stockholms förorter har ett antal personer varsin hyresrätt som de är beredda att byta bort om de får någon bättre lägenhet i utbyte. Vad som är bra för en person behöver inte vara bra för en annan, så många byten är båda parter villiga att gå med på. Ibland förekommer även triangelbyten och i princip kan man ha godtyckligt långa byteskedjor. Hur finner man optimalt lägenhetsbyte?

Litteraturförslag: "Two-sided matching" av Alvin Roth och Marilda Sotomayor, "On cores and indivisibility" av Lloyd Shapley and Herbert Scarf, Journal of Mathematical Economy (1974), 23-37. WWW: Sök på "house swapping".

Arrows diktatorsats

Arrows diktatorsats handlar om problemet med att utforma en omröstningsprocedur bland flera alternativ. Kenneth J. Arrow ("nobelpris"tagare i ekonomi 1972) bevisade att om vissa naturliga egenskaper hos omröstningsproceduren ska vara uppfyllda så är det enda teoretiskt möjliga alternativet att låta en diktator bestämma. Vill man inte ha diktatur får man finna sig i att omröstningsproceduren har andra defekter. Detta resultat har många praktiska konsekvenser, bland annat vid poängräkning i konståkning .

Litteraturförslag: "Collective Choice and Social Welfare" av Amartya K. Sen ("nobelpris"tagare), "Social Choice: A Framework for Collective Decisions and Individual Judgements" av John Craven, "Arrow's Theorem" av Alfred Mackay. WWW: Sök på "Arrow's theorem".

Matroider

Linjär algebra och grafteori möts i begreppet matroider. När man plockar vektorer ur ett ändligdimensionellt vektorrum får man till slut en beroende mängd - den sista vektorn kunde uttryckas med hjäp av de tidigare. På samma sätt får man om man plockar kanter från en ändlig graf till slut en cykel - det fanns redan en väg mellan de två hörn som den sista kanten binder samman. Matroider abstraherar denna idé.

Litteraturförslag: "Introduction to Graph Theory", kap 9, av Robin J. Wilson. WWW: Sök på "matroids".

Sidan ursprungligen skriven av Kimmo Eriksson, 1998.

Lite modifierad av Bengt Ek januari 2001, januari 2005 och september 2011.