Drawing Families of Cuts in a Graph

Zitieren

Dateien zu dieser Ressource

Prüfsumme: MD5:bbfa5e187c8e21c96d2da838b6c00429

CORNELSEN, Sabine, 2003. Drawing Families of Cuts in a Graph

@phdthesis{Cornelsen2003Drawi-591, title={Drawing Families of Cuts in a Graph}, year={2003}, author={Cornelsen, Sabine}, address={Konstanz}, school={Universität Konstanz} }

application/pdf 2003 eng Drawing Families of Cuts in a Graph 2011-03-22T17:45:09Z Ein Graph ist eine abstrakte Repräsentation relationaler Daten auf<br />einer Menge von Individuen. Ein Schnitt in einem Graphen zerteilt die<br />Menge der Individuen in zwei nicht-leere Teilmengen. In dieser Arbeit<br />werden Methoden zur Visualisierung von Schnitten und Mengen von<br />Schnitten eingeführt. Ein Schnitt enthält zwei wichtige Arten von<br />Information: die Partition der Menge der Individuen und die Relationen<br />zwischen Individuen verschiedener Teilmengen. Eine Zeichnung eines<br />Schnittes sollte beides graphisch darstellen. Aus einer Zeichnung<br />einer ganzen Familie von Schnitten sollte außerdem genau hervorgehen,<br />welche Schnitte tatsächlich gemeint sind und welche nicht. - Es werden verschiedene Ansätze vorgestellt, die die oben angedeuteten<br />Anforderungen erfüllen. In Anlehnung an Zeichenmethoden, die<br />ursprünglich für Bipartitionen, d.h. für Schnitte, für die es<br />jeweils keine Relationen zwischen Individuen der selben Teilmenge der<br />Individuenmenge gibt, entwickelt wurden, werden zunächst Zeichnungen<br />auf parallelen Linien betrachtet. Der Hauptansatz für die Zeichnung<br />von Familien von Schnitten beruht auf der Tatsache, daß eine einfache<br />geschlossene Kurve die Ebene in zwei Zusammenhangskomponenten<br />zerteilt. Ein Schnitt kann also durch eine einfache geschlossene Kurve<br />repräsentiert werden, der die beiden Teilmengen der Individuenmenge<br />trennt. Als Spezialfall werden minimale Schnitte betrachtet, d.h.<br />Schnitte, deren beide Teilmengen so wenig wie möglich miteinander<br />verbunden sind. Für die Familie aller minimalen Schnitte wird eine<br />Zeichnung mit achsenparallelen Rechtecken konstruiert. Schließlich<br />untersuchen wir das Graphmodell der minimal und minimal+1-ten<br />Schnitte eines Graphen. deposit-license Cornelsen, Sabine Cornelsen, Sabine 2011-03-22T17:45:09Z

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

final.pdf 94

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto