To Örebro University

oru.seÖrebro University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Analys av medianproblemetinom grafteori
Örebro University, School of Science and Technology.
2023 (Swedish)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [sv]

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.

Abstract [en]

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.

Place, publisher, year, edition, pages
2023. , p. 49
National Category
Mathematics
Identifiers
URN: urn:nbn:se:oru:diva-106224OAI: oai:DiVA.org:oru-106224DiVA, id: diva2:1765046
Subject / course
Mathematics
Supervisors
Examiners
Available from: 2023-06-09 Created: 2023-06-09 Last updated: 2023-06-09Bibliographically approved

Open Access in DiVA

fulltext(938 kB)110 downloads
File information
File name FULLTEXT01.pdfFile size 938 kBChecksum SHA-512
9476618b862392f5f6b9909206ac7674f552fb0b926550b75435a8b5e408c0f2013494b50307bc080a76e2a6c082f75c64f765d7be40bf7b61f9517050ffe5a6
Type fulltextMimetype application/pdf

By organisation
School of Science and Technology
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 110 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 115 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf