Uppsatser i kurs 5B1204,
Diskret matematik för D2

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

Elva 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. Be föreläsare och övningslärare om hjälp om ni har svårt att hitta litteratur. Det är ofta värt att söka på webben.

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 hamiltonstig), 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 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".

Kromatiska polynom: antalet sätt att färga grafer

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

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. Kap 2.7 i "Combiantorics and Graph Theory" av John M. Harris, Jeffry L. Hirst och Michael J. Mossinghoff. WWW: Sök på "stable matching problem".

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".

Latinska kvadrater

En latinsk kvadrat är en kvadratisk matris, med sidlängd N, sådan att var och en av N symboler förekommer exakt en gång i varje rad och i varje kolumn. Sådana dyker upp i vissa modeller, både teoretiska och praktiska. Exempelvis är varje grupptabell en latinsk kvadrat. Euler studerade problemet att finna par av så kallat ortogonala latinska kvadrater. Det är fortfarande ett öppet problem för vilka N som ortogonala latinska kvadrater existerar. Latinska kvadrater kan representeras med kantfärgningar av kompletta bipartita grafer.

Litteraturförslag: "Discrete Mathematics", kap 13.5,17.3 av Norman L. Biggs. WWW: Sök på "latin squares".

Symmetrigruppen av automorfier på en graf

En automorfi på en graf är en omnumrering av hörnen som bibehåller kantrelationerna, dvs om det fanns en kant mellan hörn nr i och nr j från början ska det fortfarande efter omnumrering finnas en kant mellan hörn nr i och nr j. En omnumrering är en permutation. Mängden av automorfier är en grupp under den vanliga multiplikationen av permutationer.

Litteraturförslag: "Discrete Mathematics", kap 21, av Norman L. Biggs. WWW: Sök på "graph automorphisms".

Heltalspartitioner

En partition av ett heltal är en uppdelning av heltalet i positiva heltalstermer. Exempelvis är 3+2+2 en partition av 7. Det finns otroligt mycket att säga om antalet partitioner av ett heltal, med eller utan begränsningar. Mest berömd är Eulers sats som säger att ett heltal kan partitioneras i udda termer på lika många sätt som det kan partitioneras i distinkta termer (alla termer olika). Exempel: 6 kan partitioneras i udda termer på fyra sätt: 5+1, 3+3, 3+1+1+1, 1+1+1+1+1+1. 6 kan även partitioneras i disktinkta termer på fyra sätt: 6, 5+1, 4+2, 3+2+1.

Litteraturförslag: "Discrete Mathematics", kap 26, av Norman L. Biggs. "Integer Partitions", av George Andrews och Kimmo Eriksson. WWW: Sök på "integer partitions".

Ramseyteori

I varje graf på 6 noder kommer det antingen att finnas 3 noder där alla (tre) möjliga kanter mellan dessa noder finns med i grafen eller 3 noder där ingen av de tre kanterna finns med. Detta gäller inte för alla grafer med fem noder (t.ex. en cykel). Vi säger att Ramseytalet R(3,3)=6. Det är klassisk sats av Ramsey att R(k,l) är ändlig för alla k och l. Det är dock förvånansvärt svårt att bestämma dessa tal exakt och asymptotiskt. Inte ens R(5,5) är känt. Många är de matematiker och lekmän som har försökt förbättra resultaten. Det finns också en uppsjö av generaliseringar.

Litteraturförslag: "Ramsey Theory" av Graham, Rotschild och Spencer; "Combinatorics and Graph Theory", kap. 1.6, av Harris, Hirst och Mossinghoff; "Dynamic Survey on Small Ramsey Numbers", av Stanislaw Radziszowski. WWW: Sök på "Ramsey theory".

Sidan ursprungligen skriven av Kimmo Eriksson, 1998.

Lite modifierad av Bengt Ek januari 2001 och januari 2005.

Ytterligare modifierad av Svante Linusson januari 2006.