Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-11367
Authors: Holderbach, Samuel
Title: Interaktive Kantenkontraktion für Minorensuche
Other Titles: Interactive Contraction of edges for minor detection
Issue Date: 2020
metadata.ubs.publikation.typ: Abschlussarbeit (Bachelor)
metadata.ubs.publikation.seiten: 42
URI: http://elib.uni-stuttgart.de/handle/11682/11384
http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-113840
http://dx.doi.org/10.18419/opus-11367
Abstract: Ein Minor ist ein Graph, der aus einem Teilgraphen eines anderen Graphen durch die Kontraktion von Kanten entsteht [Moh06]. In der Graphentheorie spielen Minoren eine äußerst wichtige Rolle. Beispielsweise kann man feststellen, ob es möglich ist, einen Graphen überschneidungsfrei in eine Ebene einzuzeichnen, indem man prüft, ob dieser weder den vollständigen Graphen K_5 noch den vollständigen bipartiten Graphen K_3,3 als Minor enthält. Trotz ihrer Relevanz für die Graphentheorie ist die Minorenrelation weniger intuitiv als zum Beispiel die Teilgraphen- oder die Unterteilungsrelation. Im Zuge meiner Bachelorarbeit habe ich deshalb ein Spiel mit dem Namen Minorfinder als Teil einer Kollektion kleiner Rätsel-Computerspiele entworfen, bei dem interaktiv Minoren in anderen Graphen gesucht werden können. Minorfinder lehnt sich dabei an Untangle an; ein Spiel, bei dem man Graphen planar in die Ebene legen muss, welches ebenfalls in der Spielekollektion zu finden ist.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
SamuelHolderbach_BScArbeit_2021.pdf582,82 kBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.