Artikel

5.4: Bipartite Graphen - Mathematik


Wir haben bereits gesehen, wie zweiteilige Graphen unter bestimmten Umständen auf natürliche Weise entstehen. Hier untersuchen wir bipartite Graphen ein wenig mehr.

Es ist leicht zu erkennen, dass alle geschlossenen Wege in einem bipartiten Graphen eine gleichmäßige Länge haben müssen, da die Knoten entlang des Weges zwischen den beiden Teilen alternieren müssen. Bemerkenswerterweise ist das Gegenteil der Fall. Wir brauchen eine neue Definition:

Definition: Abstand zwischen den Scheitelpunkten

Der Abstand zwischen den Knoten (v) und (w), (d(v,w)), ist die Länge eines kürzesten Weges zwischen den beiden. Wenn zwischen (v) und (w) kein Weg ist, ist die Entfernung undefiniert.

Satz 5.4.2

(G) ist genau dann bipartit, wenn alle geschlossenen Wege in (G) von gerader Länge sind.

Beweis

Die Vorwärtsrichtung ist einfach, wie oben besprochen.

Nehmen wir nun an, dass alle geschlossenen Wege eine gleichmäßige Länge haben. Wir können annehmen, dass (G) zusammenhängend ist; wenn nicht, behandeln wir jede angeschlossene Komponente separat.

Sei (v) eine Ecke von (G), (X) sei die Menge aller Ecken in geradem Abstand von (v) und (Y) sei die Menge der Ecken bei ungerader Abstand von (v). Wir behaupten, dass alle Kanten von (G) eine Ecke von (X) mit einer Ecke von (Y) verbinden. Angenommen, nicht; dann gibt es benachbarte Ecken (u) und (w), so dass (d(v,u)) und (d(v,w)) die gleiche Parität haben. Dann gibt es einen geschlossenen Weg von (v) nach (u) nach (w) nach (v) der Länge (d(v,u)+1+d(v,w )), was seltsam ist, ein Widerspruch.

(Quadrat)

Der geschlossene Weg, der den Widerspruch liefert, ist nicht unbedingt ein Kreislauf, aber dem kann abgeholfen werden, indem eine etwas andere Version des Theorems bereitgestellt wird.

Folgerung 5.4.3

(G) ist genau dann zweiteilig, wenn alle Zyklen in (G) von gerader Länge sind.

Beweis

Wieder ist die Vorwärtsrichtung einfach, und wieder nehmen wir an, dass (G) zusammenhängend ist. Sei nach wie vor (v) eine Ecke von (G), (X) sei die Menge aller Ecken in geradem Abstand von (v) und (Y) die Menge von Ecken mit ungeradem Abstand von (v). Wenn zwei Ecken in (X) benachbart sind oder zwei Ecken in (Y) benachbart sind, dann gibt es wie im vorherigen Beweis einen geschlossenen Weg ungerader Länge.

Um den Beweis abzuschließen, genügt es zu zeigen, dass es einen Kreis ungerader Länge gibt, wenn es einen geschlossenen Weg (W) ungerader Länge gibt. Der Beweis erfolgt durch Induktion über die Länge des geschlossenen Weges.

Wenn (W) keine wiederholten Ecken hat, sind wir fertig. Angenommen, der geschlossene Weg ist closed

$$v=v_1,e_1,ldots,v_i=v,ldots,v_k=v=v_1.$$

Dann

$$ v=v_1,ldots,v_i=v quadhbox{und}quad v=v_i,e_i,v_{i+1},ldots, v_k=v $$

sind geschlossene Rundgänge, beide sind kürzer als der ursprüngliche geschlossene Rundgang und einer von ihnen hat eine ungerade Länge. Nach der Induktionshypothese gibt es einen Zyklus ungerader Länge.

(Quadrat)

Es ist häufig fruchtbar, Grapheigenschaften im begrenzten Kontext von bipartiten Graphen (oder anderen speziellen Graphtypen) zu betrachten. Was können wir beispielsweise über Hamilton-Zyklen in einfachen bipartiten Graphen sagen? Angenommen, die Partition der Knoten des bipartiten Graphen ist (X) und (Y). Da jeder Kreis zwischen den Ecken der beiden Teile des bipartiten Graphen alterniert, gilt für einen Hamilton-Kreis (|X|=|Y|ge2). In einem solchen Fall ist der Grad jeder Ecke höchstens (n/2), wobei (n) die Anzahl der Ecken ist, nämlich (n=|X|+|Y|). Somit ist die Erzbedingung ()d(v)+d(w)ge n), wenn (v) und (w) nicht benachbart sind) äquivalent zu (d(v)= n/2) für alle (v). Dies bedeutet, dass der einzige einfache bipartite Graph, der die Erzbedingung erfüllt, der vollständiger zweiteiliger Graph (K_{n/2,n/2}), wobei die beiden Teile die Größe (n/2) haben und jede Ecke von (X) an jede Ecke von (Y) angrenzt. Das Ergebnis ist, dass die Ore-Eigenschaft keine interessanten Informationen über bipartite Graphen liefert.

Wie bei allgemeineren Graphen gibt es natürlich auch bipartite Graphen mit wenigen Kanten und einem Hamilton-Zyklus: Jeder Zyklus gerader Länge ist ein Beispiel.

Wir bemerken, dass im Allgemeinen ein vollständiger bipartiter Graph (K_{m,n}) ein bipartiter Graph mit (|X|=m), (|Y|=n) und jeder Ecke von . ist (X) grenzt an jede Ecke von (Y). Die einzigen solchen Graphen mit Hamilton-Zyklen sind solche mit (m=n).


Schau das Video: What is a Bipartite Graph? Graph Theory (September 2021).