5.2.6. Planar eingebettete Graphen, Maps und Faces

Lernziele

Planare Graphen und planare Einbettungen
Bidirektionale Graphen und Maps
Face-Zyklen und Faces
Ordnungserhaltende Einbettungen und ebene Maps
Die Funktionen Is_Plane_Map() und PLANAR()

Graphen dienen dazu, Beziehungen zwischen Objekten festzuhalten. Einem Rechner genügt dazu die kombinatorische Struktur der Knoten und Kanten, festgehalten in den einzelnen Adjazenzlisten; wir als Menschen dagegen bevorzugen Zeichnungen, mit Hilfe derer wir uns schnell einen Überblick verschaffen können. Das Zeichnen von Graphen ist daher ein wichtiges Thema. Wir beschäftigen uns hier mit Zeichnungen, die auf einem Blatt Papier, also in der zweidimensionalen Anschauungsebene, stattfinden. (Graphen werden bisweilen auch auf eine Kugel oder einen Torus gezeichnet - man denke etwa an die Ländergrenzen auf einem Globus; diese Art von Zeichnungen sind hier nicht weiter von Interesse.)

Planare Einbettungen

Es gibt natürlich unendlich viele Möglichkeiten, einen Graphen auf ein Blatt Papier (genauer: in die zweidimensionale Anschauungsebene) zu zeichnen. Von allen diesen sind vor allem diejenigen Zeichnungen interessant, bei denen sich die Kanten nicht überschneiden, alleine schon deshalb, weil sie für das Auge am wenigsten verwirrend sind. Eine solche Zeichnung heißt planare Einbettung (planar embedding). Ein Graph heißt planar, wenn er eine planare Einbettung besitzt. Bei Weitem nicht jeder Graph ist planar. So sind z. B. die kleinsten, nicht-planaren Graphen die beiden aus Abbildung 5.10. Der linke ist der vollständige Graph vom Grad 5, der als K5 bezeichnet wird; der rechte ist der vollständige bipartite Graph mit 3 Knoten in jeder Teilmenge und wird als K3,3 bezeichnet. (Ein Graph heißt bipartit, wenn die Knoten so in zwei Teilmengen A und B zerfallen, dass für jede Kante der Quell- und der Zielknoten in verschiedenen Teilmengen liegen.)

Abbildung 5.10. Die nicht-planaren Kuratowski-Graphen K5 und K3,3

Die nicht-planaren Kuratowski-Graphen K5 und K3,3

Die kleinsten nicht-planaren Graphen. Ein Graph ist genau dann nicht planar, wenn er eine Unterteilung des K5 oder des K3,3 als Teilgraph enthält.

Eines der berühmtesten Ergebnisse der Graphentheorie ist der Satz, dass ein Graph genau dann nicht planar ist, wenn er eine Unterteilung des K5 oder des K3,3 als Teilgraph enthält. Eine Unterteilung (subdivision) eines Graphen entsteht dadurch, dass Kanten unterteilt werden. Eine Kante zu unterteilen bedeutet, sie in zwei Kanten aufzuspalten, indem ein neuer Knoten auf der Kante eingefügt wird, so dass die alte Kante durch zwei neue ersetzt wird. Dieser Satz wurde zuerst von dem polnischen Mathematiker Kazimierz Kuratowski bewiesen; ihm zu Ehren heißen die beiden Graphen aus Abbildung 5.10 auch Kuratowski-Graphen.

Dieser Abschnitt erklärt LEDAs Sichtweise von planar eingebetteten Graphen und der damit zusammenhängenden Konzepte.

Landkarten und Gebiete im täglichen Leben

Im täglichen Leben begegnen uns oft Landkarten wie die aus Abbildung 5.11. Diese zeigen ein polygonales Netz in der Ebene, d. h., die Kanten eines planar eingebetteten Graphen bilden eine (endliche) Menge aneinander grenzender Polygone. Jedes dieser Polygone steht für ein Land oder Gebiet auf der Landkarte. Die Landkarte aus Abbildung 5.11 stellt das Heimatland von LEDA dar, das schöne Saarland. Die Karte zeigt 7 Gebiete: die 6 Landkreise des Saarlandes und „den Rest der Welt“. Dieser Rest der Welt wird ebenfalls als Gebiet angesehen, als das so genannte äußere Gebiet.[39]

Abbildung 5.11. Das Saarland als Graph

Das Saarland als Graph

Das Saarland besteht aus 6 Gebieten. Das äußere Gebiet umfasst alles, was nicht im Saarland liegt. Diese Landkarte zeigt also 7 Gebiete. Der Graph ist planar eingebettet; daher ist der Graph planar. Es gibt viele andere Möglichkeiten, den Graphen zu zeichnen, darunter auch viele, die keine planare Einbettung darstellen!

Bidirektionale Graphen

Wie ist LEDAs Sichtweise von solchen Landkarten? Wie werden sie kodiert? Aus verschiedenen Gründen, auf die wir hier nicht näher eingehen wollen, ist die Datenstruktur der Wahl ein bidirektionaler Graph, bei dem jede Kante eine entsprechende Rückwärtskante kennt. Wir erweitern unsere bisherige Definition eines bidirektionalen Graphen auf folgende:

Ein gerichteter Graph heißt bidirektional, wenn Folgendes gilt: Es gibt eine Abbildung reversal(), die jeder Kante e=(v,w) eine Gegenkante (reversal edge) reversal(e) zuordnet, so dass Folgendes gilt:

  1. reversal(e)=(w,v), d. h., die Gegenkante zu e ist tatsächlich umgekehrt gerichtet und reversal() verdient seinen Namen.

  2. reversal(reversal(e))=e, d. h., auch wenn Multikanten vorhanden sind, entsprechen immer zwei Kanten einander.

  3. e ist verschieden von reversal(e); d. h., wenn Selbstschleifen vorhanden sind, hat jede Selbstschleifenkante eine andere Selbstschleifenkante als Gegenkante.

  4. Jede Kante e kommt als Gegenkante reversal(e') einer anderen Kante vor e', d. h., die Abbildung ist bijektiv.

Wie erzeugen wir nun einen solchen bidirektionalen Graphen? Natürlich können wir explizit zu jeder Kante auch die entsprechende Gegenkante einfügen; viel einfacher ist es aber, nur jeweils eine Kante eines Paares einzufügen und

G.make_bidirected();

aufzurufen. Diese Methode fügt zu G eine minimale Anzahl von Kanten hinzu, so dass G bidirektional wird.

Ob ein Graph bereits bidirektional ist, kann mit

G.is_bidirected();

getestet werden.

Abbildung 5.12 zeigt den Graphen aus Abbildung 5.11 als bidirektionalen Graphen. Die Bedeutung der Zahlen an den Kanten wird bald ersichtlich werden.

Abbildung 5.12. Das Saarland als bidirektionaler Graph

Das Saarland als bidirektionaler Graph

Kanten mit gleicher Zahlenbeschriftung liegen im selben Face-Zyklus.

Maps

LEDAs Kodierung eines eingebetteten Graphen umfasst aber noch mehr: Jede Kante muss ihre (eindeutige) Gegenkante kennen. Ein solcher Graph wird als Map bezeichnet. Abbildung 5.13 zeigt eine solche Map

Abbildung 5.13. Eine Map

Eine Map

Folgende Paare von Kanten bilden Gegenkanten zueinander: a und b, c und d, e und f, g und h, i und j. Es wären auch die Beziehungen reversal(g)=j und reversal(h)=i denkbar. Es sei z. B. adj_edges(0)=(h,j,f), adj_edges(1)=(g,c,i) und adj_edges(2)=(e,a,b,d). Dann gibt es die Face-Zyklen [h,i], [j,c,b,e], [f,d,g] und [a]

Um aus einem bidirektionalen Graphen eine Map zu erhalten, muss für jede Kante e die Gegenkante gesetzt werden. Dafür gibt es zwei Möglichkeiten: Die erste besteht darin, einen bidirektionalen Graphen durch einen Aufruf von

G.make_map();

zu einer Map zu machen. Diese Methode liefert false zurück, falls der Graph nicht bidirektional ist. Diese Methode erhält schon gesetzte Gegenkantenbeziehungen, d. h., wenn f=reversal(e) vor dem Aufruf schon gilt, so auch danach.

Die zweite Möglichkeit besteht darin, für jede Kante e die Gegenkante f=reversal(e) explizit selbst zu setzen. Dazu dient die Anweisung

G.set_reversal(e,f);

die gleichzeitig f als Gegenkante zu e und umgekehrt e als Gegenkante zu f festlegt. Diese Methode prüft zunächst, ob die beiden Kanten überhaupt zulässige Gegenkanten voneinander sein können, und tut nichts, falls dem nicht so ist. Wenn die Gegenkante e'=reversal(e) von e vorher schon gesetzt wurde, wird die Gegenkante von e' auf nil gesetzt. Dasselbe gilt für eine schon gesetzte Gegenkante von f.

Face-Zyklen

Es fehlt noch ein letzter Baustein, um LEDAs Sichtweise von planar eingebetteten Graphen vollständig zu verstehen. Letztendlich wollen wir in einer planaren Einbettung so etwas sagen können wie „Das Gebiet X ist genau dasjenige Gebiet, das von folgenden Kanten umgrenzt wird: ...“ und dann die Kanten in der entsprechenden Reihenfolge durchlaufen. Die Gebiete einer Einbettung werden als Faces bezeichnet. Sie ergeben sich dadurch, dass bestimmte (angrenzende) Kanten in einer bestimmten Reihenfolge (einem Zyklus) durchlaufen werden; zu dem jeweiligen Gebiet gehört alles, was in einem intuitiven Sinne „links von allen Kanten“ des Zyklus liegt. Dazu definieren wir zunächst einmal den Begriff des „Face-Zyklus“:

Die aus jedem Knoten v ausgehenden Kanten liegen in dessen Adjazenzliste adj_edges(v); da es sich dabei intern um eine zirkuläre Liste handelt, liegen sie dort in einer bestimmten Reihenfolge. Daher können wir zu einer Kante e den zyklischen Nachfolger und den zyklischen Vorgänger in der Liste adj_edges(Quelle(e)) bestimmen. Für eine Kante e liefern

G.cyclic_adj_succ(e);
G.cyclic_adj_pred(e);

diesen Nachfolger bzw; Vorgänger in der zyklischen Adjazenzliste von Quelle(e). Wir definieren nun den Face-Zykus-Nachfolger bzw. den Face-Zyklus-Vorgänger als

G.face_cycle_succ(e) == G.cyclic_adj_pred(G.reversal(e));
G.face_cycle_pred(e) == G.cyclic_adj_succ(G.reversal(e));

Diese Definition hat natürlich nur in einer Map G Gültigkeit, denn nur dort ist die Information G.reversal(e) immer vorhanden.

Ein Face-Zyklus entsteht nun dadurch, dass ausgehend von einer Kante e=e0 immer zum nächsten Face-Zyklus-Nachfolger ei+1=face_cycle_succ(ei) übergegangen wird. Ohne Beweis wollen wir festhalten, dass wir so immer wieder zur Kante e zurückkommen, dass e die erste Kante ist, die in der so erzeugten Kantenfolge zum zweiten Mal auftritt, und dass jede Kante der Map in genau einem Face-Zyklus liegt (s. Übung 58). Die Face-Zyklen teilen also die Kantenmenge E eines Graphen in disjunkte Teilmengen auf.

Als Beispiel gehen wir in Abbildung 5.13 davon aus, dass die Ordnung der Kanten in den Adjazenzlisten wie folgt lautet: adj_edges(0)=(h,j,f), adj_edges(1)=(g,c,i) und adj_edges(2)=(e,a,b,d). Dann ergibt sich der Face-Zyklus, in dem die Kante j liegt, wie folgt:

face_cycle_succ(j) = cyclic_adj_pred(reversal(j)) 
                   = cyclic_adj_pred(i) = c,
face_cycle_succ(c) = cyclic_adj_pred(reversal(c)) 
                   = cyclic_adj_pred(d) = b.
face_cycle_succ(b) = cyclic_adj_pred(reversal(b)) 
                   = cyclic_adj_pred(a) = e.
face_cycle_succ(e) = cyclic_adj_pred(reversal(e)) 
                   = cyclic_adj_pred(f) = j.

Dadurch ergibt sich der Face-Zyklus [j,c,b,e]. Entsprechend ergeben sich die anderen Face-Zyklen [h,i], [f,d,g] und [a].

[Important] Wichtig

Es handelt sich bei den Face-Zyklen zunächst um rein kombinatorische Strukturen, die abhängig von der Ordnung der Kanten in den Adjazenzlisten sind. Unterschiedliche Ordnungen in den Adjazenzlisten ergeben i. Allg. unterschiedliche Face-Zyklen. Ein Face-Zyklus entspricht nicht immer einem Face eines eingebetteten Graphen!

Diese Aussage wird durch Abbildung 5.14 erhärtet. Dort sind alle Kanten, die im selben Face-Zyklus liegen, mit derselben Nummer beschriftet. Offenbar ist der Face-Zyklus mit der Nummer 4 kein Face des Graphen, wenn man diesen als in die Ebene eingebettet betrachtet. Dasselbe gilt für den Face-Zyklus mit der Nummer 1 aus Abbildung 5.12.

Abbildung 5.14. Maps und Face-Zyklen

Maps und Face-Zyklen

Um LEDAs Schnittstelle zu Maps und Face-Zyklen zu beschreiben, zeigen wir ein Programm, mit dem der Benutzer interaktiv einen Graphen eingeben und die Face-Zyklen darin sichtbar machen kann: Kanten desselben Face-Zyklus werden mit derselben Nummer beschriftet und in derselben Farbe gezeichnet. Abbildung 5.14 wurde damit erzeugt. Das Programm erweitert zusätzlich unsere Kenntnisse der Schnittstelle von GraphWin. Der Leser möge mit diesem Programm so lange spielen, bis er ein intuitives Verständnis von Face-Zyklen entwickelt hat!

Filename: MapsAndFaceCycles.C
#include <LEDA/graph.h>
#include <LEDA/graphwin.h>
#include <LEDA/color.h>
#include <LEDA/string.h>

using leda::graph;
using leda::face;
using leda::edge;
using leda::GraphWin;
using leda::window;
using leda::color;
using leda::string;
using std::cout;


int main()
{
  graph G;

  GraphWin gw(G, 500, 500, "Maps and Face Cycles");
  gw.set_edge_label_type(leda::user_label);
  gw.set_edge_label_pos(leda::west_pos);
  gw.set_flush(false);
  gw.display(window::center,window::center);

  while(gw.edit()) { 

    G.make_bidirected();
    G.make_map();
    G.compute_faces();

    gw.update_graph();

    int num_face = 0;
    face f;
    forall_faces(f,G) {
      num_face++;
      edge e;
      forall_face_edges(e,f) {
        gw.set_color(e, color(num_face % 16));
        gw.set_label_color(e, color(num_face % 16));
        gw.set_user_label(e, string("%d",num_face));
      }
    }
   
    gw.redraw();
  }
}

Wir machen in jedem Edit-and-Run-Zyklus den vom Benutzer editierten Graphen G bidirektional und bauen dann daraus eine Map. (Der Benutzer muss also keine Rückwärtskanten eingeben; zudem erlaubt es ein GraphWin nicht, die Gegenkantenbeziehungen zu setzen.)

Ein Aufruf von

G.compute_faces();

berechnet daraus die Face-Zyklen von G. Über diese kann mit dem Makro

forall_faces(f,G)

iteriert werden. Der entsprechende Datentyp von LEDA heißt face.

Jeder Face-Zyklus f besteht aus Kanten. Über diese kann mit dem Makro

forall_face_edges(e,f)

iteriert werden. Durch Verschachteln der beiden Makros können also alle Face-Zyklen Kante für Kante durchlaufen werden.

Was das GraphWin angeht, so müssen wir ihm hier nach den Änderungen, die wir außerhalb von edit() am zugrunde liegenden Graphen G vornehmen, durch update_graph() zwingend mitteilen, dass es seine internen Strukturen anpassen soll. Vergessen wir dies, so kann das Programm abstürzen!

Zur Beschriftung der Kanten setzen wir das Attribut user_label, zur farblichen Markierung das Attribut label_color. Dass wir überhaupt das benutzer-definierte Label als Beschriftung verwenden wollen, und wo dieses erscheinen soll, legen wir zuerst durch

gw.set_edge_label_type(leda::user_label);
gw.set_edge_label_pos(leda::west_pos);

fest. Da der Graph nicht nach jeder Beschriftungs- und Färbungsoperation neu gezeichnet werden soll, setzen wir zunächst den flush-Parameter auf false und zeichnen am Ende der Schleife mit redraw() alles neu.

Ordnungserhaltende Einbettungen

Wir kommen nun zum dem Punkt, auf den wir im ganzen Abschnitt hingearbeitet haben: planar eingebettete Graphen und LEDAs Sichtweise davon. Wann können wir einen Graphen so in die Ebene zeichnen, dass sich keine Kanten überschneiden, und wie können wir dann auf die einzelnen Gebiete zugreifen? Wir sagten oben schon, dass Maps die Datenstruktur der Wahl für planar eingebettete Graphen sind.

Wenn in einer planaren Einbettung einer Map, d. h. einer Zeichnung derselben, in der sich keine Kanten überschneiden, für jeden Knoten v die Ordnung der Kanten um v herum (im Gegenuhrzeigersinn) mit der Ordnung der Kanten in der Adjazenzliste adj_edges(v) übereinstimmt, so heißt die Einbettung ordnungserhaltend (order preserving embedding). Die Einbettung der Map aus Abbildung 5.13 ist nicht ordnungserhaltend, weil z. B. die Reihenfolge h, f, j der Kanten um den Knoten 0 herum nicht der Reihenfolge h, j, f in der Adjazenzliste adj_edges(0) entspricht. In einer ordnungserhaltenden Einbettung einer Map entsprechen die Face-Zyklen der Map immer genau den Faces (also den Gebieten) der Einbettung.

Eine Map heißt eben (plane), wenn sie eine ordnungserhaltende, planare Einbettung besitzt. Die Map aus Abbildung 5.13 ist eben; dazu muss nur die Reihenfolge der Kanten in den Adjazenzlisten so umgeändert werden, dass sie mit der Reihenfolge in der Einbettung übereinstimmt. Es gibt aber durchaus Maps, die nicht eben sind. Ein Aufruf von

G.Is_Plane_Map();

testet, ob G eine ebene Map ist. Die einzubindende Header-Datei ist graph_misc.h.

Das ist aber i. Allg. nicht das, was wir wollen. Vielmehr wollen wir meistens von einem beliebigen Graphen G entscheiden, ob er planar ist, und wenn ja, dann wollen wir eine planare Einbettung davon zeichnen lassen. Das Zeichnen von Graphen werden wir erst in Abschnitt 5.3.8 besprechen. Ob ein Graph aber überhaupt planar ist, können wir mit

PLANAR(G,embed);

testen. G darf dabei keine Selbstschleifen enthalten. Die einzubindende Header-Datei heißt plane_graph_alg.h. Das Default-Argument embed steht auf false; wird es als true übergeben und ist G tatsächlich planar, so ordnet PLANAR() zusätzlich die Kanten in den Adjazenzlisten von G so um, dass G eine ebene Map wird. Das bedeutet, dass die Kanten um die Knoten herum nun so angeordnet sind, dass sie der Anordnung in einer Zeichnung entsprechen, in der sie sich nicht überschneiden. Weiterhin bedeutet es, dass die Face-Zyklen der so erhaltenen Map den Faces (also den Gebieten) einer planaren Einbettung entsprechen.

Das folgende Programm macht fast dasselbe wie das obige. Zusätzlich aber testet es, ob der vom Benutzer eingegebene Graph planar ist, und wenn ja, dann berechnet es eine ebene Map daraus. Das heißt aber noch nicht, dass es eine planare Einbettung des Graphen berechnet. Vielmehr macht es die Face-Zyklen einer möglichen planaren Einbettung sichtbar.

Filename: PlanarityTest.C
#include <LEDA/graph.h>
#include <LEDA/graphwin.h>
#include <LEDA/plane_graph_alg.h>
#include <LEDA/color.h>
#include <LEDA/string.h>

using leda::graph;
using leda::face;
using leda::edge;
using leda::GraphWin;
using leda::window;
using leda::color;
using leda::string;
using std::cout;


int main()
{
  graph G;

  GraphWin gw(G, 500, 500, "Planarity Testing");
  gw.set_edge_label_type(leda::user_label);
  gw.set_edge_label_pos(leda::west_pos);
  gw.set_flush(false);
  gw.display(window::center,window::center);

  while(gw.edit()) { 

    G.make_bidirected();
    G.make_map();
    gw.update_graph();

    bool is_planar = PLANAR(G, true);

    G.compute_faces();

    int num_face = 0;
    face f;
    forall_faces(f,G) {
        num_face++;
        edge e;
        forall_face_edges(e,f) {
          gw.set_color(e, color(num_face % 16));
          gw.set_label_color(e, color(num_face % 16));
          gw.set_user_label(e, string("%d",num_face));
        }
    }
    gw.redraw();

    if(is_planar) 
      gw.message("This Graph is planar. Click <done> to continue.");
    else
      gw.message("This Graph is not planar. Click <done> to continue.");

    gw.wait(); // waits until done is pressed
    gw.del_message(); 
  }
}

Abbildung 5.15 zeigt die Ausgabe dieses Programms für die ursprüngliche Map aus Abbildung 5.12. Die beiden Maps unterscheiden sich in der Anordnung ihrer Adjazenzlisten; dadurch ergeben sich unterschiedliche Face-Zyklen.

Abbildung 5.15. Das Saarland als ebene Map

Das Saarland als ebene Map

Der Graph ist planar. Das Programm hat eine ebene Map berechnet und die Face-Zyklen sichtbar gemacht. Diese entsprechen aber nicht den Faces der gezeigten planaren Einbettung des Graphen. So sind z. B. die Kanten des Zyklus mit Nummer 3 hier im Uhrzeigersinn gezeichnet; das von ihnen umgrenzte Face würde also „außerhalb“ des Zyklus liegen.

Faces und Face-Zyklen

Dennoch entsprechen auch hier die Face-Zyklen nicht den Face-Zyklen der gezeigten planaren Einbettung des Graphen. Wir hatten auch nur behauptet, dass unser Programm die Face-Zyklen einer möglichen planaren Einbettung sichtbar macht.

[Warning] Warnung

Wenn man von einem planar gezeichneten Graphen ausgeht und von PLANAR() eine ebene Map berechnen lässt, so kann es durchaus sein, dass die Face-Zyklen der so berechneten Map nicht mit den Faces der ursprünglichen Zeichnung übereinstimmen.

Wie ist das möglich? Wir hatten oben schon erwähnt, dass zu einem Face alles gehört, was links von allen Kanten des umgebenden Face-Zyklus liegt. Die Kanten des zu einem Face einer planaren Einbettung gehörigen Face-Zyklus müssen also im Gegenuhrzeigersinn angeordnet sein - mit Ausnahme der Kanten des äußeren Faces, die im Uhrzeigersinn angeordnet sind.

In Abbildung 5.15 sind aber z. B. die Kanten des Face-Zyklus mit der Nummer 3 im Uhrzeigersinn angeordnet. Daher können diese Face-Zyklen nicht den Faces der gezeigten planaren Einbettung entsprechen.

LEDAs Fuktion PLANAR() behauptet aber stolz, eine ebene Map zu berechnen, wenn der Graph planar ist! Wie passt das zusammen? Nun, es gibt zwei mögliche Erklärungen hierfür:

  1. Der in Abbildung 5.15 gezeigte Graph ist zwar planar eingebettet, aber diese Einbettung entspricht nicht der von PLANAR() berechneten ebenen Map, d. h., es gibt eine andere Einbettung (also eine andere Art, den Graphen planar zu zeichnen), in der die Face-Zyklen in der „richtigen“ Umlaufsrichtung gezeichnet sind, auch wenn diese Einbettung möglicherweise völlig anders aussieht als die ursprüngliche.

    Abbildung 5.16 zeigt eine solche Einbettung des Saarland-Graphen, die völlig anders aussieht als die ursprüngliche Einbettung, in der aber die Face-Zyklen aus Abbildung 5.15 tatsächlich jeweils einem Face der Einbettung entsprechen.

  2. Der Graph besitzt noch eine andere ebene Map, in der die Face-Zyklen den Faces der Einbettung entsprechen, die aber zufälligerweise leider nicht von einem Aufruf von PLANAR() berechnet wird.

    Das ist in Abbildung 5.15 der Fall. Eine solche Map kann ganz einfach aus der dort abgebildeten gewonnen werden, indem die Richtung aller Kanten umgedreht wird.

Abbildung 5.16. Eine ebene Map des Saarlands, die mit einer planaren Einbettung übereinstimmt.

Eine ebene Map des Saarlands, die mit einer planaren Einbettung übereinstimmt.

Jeder Face-Zyklus entspricht einem Face der planaren Einbettung. Der Face-Zyklus 1 entspricht dem äußeren Face, also dem Rest der Welt. Die Map ist dieselbe wie die aus Abbildung 5.15. Die Einbettung sieht aber leider gar nicht mehr wie das Saarland aus.

Laufzeiten

make_bidirected(), make_map() und compute_faces() benötigen Laufzeit O(n+m).

Übungen

Übung 58.

Überlegen Sie sich, warum in einer Map, ausgehend von einer Kante e, die sukzessive Anwendung von face_cycle_succ() wieder zu e zurückführt, warum e die erste Kante ist, die in der so erzeugten Kantenfolge zum zweiten Mal auftritt, und warum jede Kante der Map in genau einem Face-Zyklus liegt.

Übung 59.

Erzeugen Sie in obigem Programm zum Planaritätstest den Graphen K5. Testen Sie auf Planarität. Entfernen Sie dann eine beliebige Kante (genauer: ein beliebiges Paar aus Kante und Gegenkante) aus dem Graphen und testen Sie nochmals. Benutzen Sie die Nummerierung und die farbliche Information der Face-Zyklen, um eine planare Einbettung von Hand (d. h. durch Verschieben der Knoten mit der Maus) herzustellen. Wiederholen Sie das ganze für den Graphen K3,3.

Übung 60.

Erzeugen Sie mit random_graph() zufällige große Graphen für eine feste Anzahl n von Knoten und eine feste Anzahl m von Kanten, und bestimmen Sie experimentell die Wahrscheinlichkeit, dass ein Graph mit n Knoten und m Kanten planar ist. Wie verhalten sich die Wahrscheinlichkeiten mit wachsendem m?



[39] Der deutsche Teil des äußeren Gebietes wird im Saarland auch als „Reich“ bezeichnet, ein Ausdruck, der zum Glück keinen Eingang in die Nomenklatur der Graphentheorie gefunden hat.




Imprint-Dataprotection