Analys av medianproblemetinom grafteori

Sammanfattning: Medianproblemet innebär att, givet ett avståndsmått, hitta en permutationmed minsta totalavstånd till en mängd permutationer. Tidigare har fleraolika avståndsmått studerats och visat sig variera kraftigt i användbarhet.Permutationerna kan ses som hörn i en graf, där kanter dras mellan de somkan omvandlas till varandra genom en enda operation. I denna uppsats analyseras medianproblemet på olika typer av grafer för att identifiera vad somskiljer sig gällande medianen beroende på vilken graf som undersöks. Avståndsfunktionen som används beror på grafens struktur, och genom attjämföra bra respektive dåliga grafer dras slutsatser om vilka egenskaper hosgrafer som leder till mest intressant information när det kommer till mediansökning. Vid större beräkningar används Matlab för att kunna analyseragrafer av högre dimensioner. Sökandet efter medianer används bland annatinom evolutionslära för att hitta närmsta gemensamma förfäder till arter ochpå så vis kunna bygga upp evolutionära släktträd.