Graphen - Anzahl Flächen

Hallo ich bin immer wieder verwirrt und erbitte mal Hilfe bei einem Problem.

Ursache:

1. ein vollständiger Graph mit 3 Knoten (also ein Dreieck) ist ja auf jeden Fall planar, also muss es 2 Flächen geben.

ok ich kann innen und außen betrachten.

2. ein vollständiger graph mit 4 knoten ist auch noch planar und hat demnach 4 Flächen, hier ist "außen" wenn ich das in der ebene aufmale nicht mit drin, wenn ich mir das aber auf eine kugel projiziert vorstelle kann ich mir das auch noch erklären, aber nun folgendes:

Wie zähle ich in einem beliebigen Graphen die Flächen?

Ich jedenfalls bin daran gescheitert beim "Wasserwerksgraphen" (also der vollständige bipartite Graph mit 3 Knoten in beiden Mengen, also K_3,3) die Flächenanzahl zu bestimmen.

Gibt es dafür eine bestimmte Technik?
Smileys (freu)
:xmas1:
:xmas2:

shisha schrieb:

2. ein vollständiger graph mit 4 knoten ist auch noch planar und hat demnach 4 Flächen, hier ist "außen" wenn ich das in der ebene aufmale nicht mit drin, wenn ich mir das aber auf eine kugel projiziert vorstelle kann ich mir das auch noch erklären, aber nun folgendes:

x----x----
|\ 2 |   |
| \  |   |
|  \ | 3 |   4
| 1 \|   |
x----x----

x = Knoten, ich zähle vier Flächen, Nr. 4 ist "aussen". Oder verstehe ich was falsch?

Christoph

shisha schrieb:

1. ein vollständiger Graph mit 3 Knoten (also ein Dreieck) ist ja auf jeden Fall planar, also muss es 2 Flächen geben.

Ja, obwohl mir die Schlussfolgerung "ist planar, also muss es 2 Flächen geben" nicht klar ist.

shisha schrieb:

ok ich kann innen und außen betrachten.

Genau.

shisha schrieb:

2. ein vollständiger graph mit 4 knoten ist auch noch planar und hat demnach 4 Flächen, hier ist "außen" wenn ich das in der ebene aufmale nicht mit drin, wenn ich mir das aber auf eine kugel projiziert vorstelle kann ich mir das auch noch erklären, aber nun folgendes:

Nein, natürlich zählt man die Fläche "außenrum" immer mit. Das wäre ziemlich unverständlich, wenn man die mal mitzählt und mal nicht. Den vollständigen Graphen mit 4 Knoten musst du dir planar aufmalen, damit du 4 Flächen bekommst. Du darfst ihn dir also nicht so aufmalen, dass sich zwei Kanten irgendwo überschneiden, sonst bekommst du mit Sicherheit ein falsches Ergebnis.

shisha schrieb:

Wie zähle ich in einem beliebigen Graphen die Flächen?

Ich jedenfalls bin daran gescheitert beim "Wasserwerksgraphen" (also der vollständige bipartite Graph mit 3 Knoten in beiden Mengen, also K_3,3) die Flächenanzahl zu bestimmen.

Da K_{3,3} nicht mehr planar ist, kannst du dort keine Flächen zählen.

Ach ja... hat das nicht irgendwas mit einer Formel von Euler zu tun? Dunkel erinnere ich mich...

volkard

Mups schrieb:

Ach ja... hat das nicht irgendwas mit einer Formel von Euler zu tun? Dunkel erinnere ich mich...

Und ich wollte gerade anfangen, drüber nachzudenken. :xmas1:

Jester

Hallo,

bei planaren Graphen, also denen, die sich ohne Kreuzung in die Ebene zeichnen lassen gibt es ein einfaches Mittel festzustellen, wieviele Flächen es gibt: Es gilt nämlich die Eulerformel für planare Graphen mit n Knoten, m Kanten und f Facetten (Flächen) gilt n-m+f=2. Das heißt egal wie Du das ganze in die Ebene zeichnest, es wird immer dieselbe Facettenzahl rauskommen. Dabei ist es übrigens egal, ob Du auf die Kugel oder in die Ebene zeichnest, diesbezüglich sind Kugel und Ebene nämlich äquivalent. Deinen Einwand bei K_4 kann ich übrigens nicht verstehen, der hat doch genau vier Facetten: drei Innere und eine Äußere.

Allerdings funktioniert der obige Ansatz nur für planare Graphen, genau da stößt Du mit dem K_3,3 auf Probleme. Du müßtest also erstmal festlegen was dann überhaupt Flächen sein sollen, wenn Du die zählen möchtest. Dazu gibt es sicher mehr als eine Möglichkeit. Du könntest zum Beispiel auf einer anderen Fläche planar einbetten -- den K_3,3 zum Beispiel auf dem Torus und dann die Flächen zählen. Dort gilt dann eine verallgemeinerte Eulerformel, nämlich n-m+f=2-2g wobei g der Genus ist -- sofern die Fläche orientierbar ist (also nicht sowas wie Möbiusband/Kleinsche Flasche). Allerdings hängt die Flächenanzahl so halt von der Fläche ab in der Du einbettest und Du hast das Problem zu testen, ob sich ein Graph mit Genus g einbetten lässt bzw. was der kleinste Genus g ist, mit dem sich der Graph einbetten lässt. Letzteres ist leider ein ziemlich schwieriges Problem.

Eine Alternative wäre eine kreuzungsminimale Zeichnung zu nehmen und an den Kreuzungen neue Punkte einzufügen und dann die Flächenzahl des entstehenden planaren Graphen anzuschaun. Leider ist auch das sehr sehr schwierig auszurechnen und es hängt davon ab, ob Du geradlinige Zeichnungen betrachtest oder die Kanten auch durch Kurven beschrieben werden können.

für mich wäre dann nur noch eines wichtig:

In wie viele Flächen können n kanten maximal erzeugen und wieso?

Christoph

shisha schrieb:

für mich wäre dann nur noch eines wichtig:

In wie viele Flächen können n kanten maximal erzeugen und wieso?

Da sich niemals zwei Kanten überschneiden, erzeugt jede neue Kante höchstens eine neue Fläche: Entweder zerteilt sie eine alte Fläche in zwei Hälften oder sie unterteilt keine Fläche (und bekommt neue Knoten).

Mit 1 Kante hast du 1 Fläche, also kannst du mit m Kanten maximal m Flächen erreichen, egal wie der Graph aussieht (vorausgesetzt, m > 0). Diese Schranke ist allerdings nicht streng in dem Sinne, dass du mit m Kanten auch wirklich m Flächen bekommen kannst (warum?). Aber ist eine einfach einzusehende obere Schranke, vielleicht reicht dir das ja schon.

Jester

shisha schrieb:

für mich wäre dann nur noch eines wichtig:

In wie viele Flächen können n kanten maximal erzeugen und wieso?

Du meinst wieviele Facetten ein planarer Graphen maximal haben kann? Das sind höchstens 2n-4. Beweis geht in etwa so: sei f_i die Anzahl der Facetten mit i Kanten auf dem Rand. Zählt man nun die Kanten über die Facetten, so wird jede Kante genau zweimal gezählt: einmal von rechts, einmal von links:

$\sum_{i \ge 3} i f_i = 2m$

$\sum_{i \ge 3} i f\_i \ge 3 \cdot \sum\_{i \ge 3} f_i = 3f$

Insgesamt also 3f <= 2m. Wenn man das in die Eulerformel steckt, bekommt man genau die obige Abschätzung (oder durch 3 teilen und du hast die Abschätzung über die Kanten). Diese Abschätzungen sind auch scharf, jede Triangulierung (also jede Facette ist Dreieck) erfüllt diese Ungleichungen mit Gleichheit.