Drawing Families of Cuts in a Graph

Abstract

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.