Analys av medianproblemetinom grafteori

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.Given a distance measure, the median problem involves finding a permutation with the smallest total distance to a set of permutations. Previously,several distance measures have been studied and found to vary significantlyin usefulness. The permutations can be seen as vertices in a graph, whereedges are drawn between the ones that can be transformed into each otherby using one single operation. In this paper the median problem is analyzedon different types of graphs in order to identify what differs regarding themedian depending on which graph that is being examined. The distance function that is used depends on the structure of the graph, and by comparinggood and bad graphs, conclusions are drawn about what properties of thegraphs that leads to the most interesting information when it comes to thesearch for medians. For large calculations Matlab is used in order to analyze graphs of higher dimensions. The search for medians is used, among otherthings, in evolutionary theory to find closest common ancestors of speciesand thus be able to build evolutionary trees