Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]

Mathematik-Online-Lexikon:

Bipartiter Graph


A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht

Ein Graph $ G$ heißt bipartit, wenn sich die Knotenmengen $ V$ so in zwei disjunkte Mengen $ A$ und $ B$ zerlegen lässt, dass es innerhalb von $ A$ und innerhalb von $ B$ keine Kanten gibt, d.h. dass jede Kante genau eine Ecke in $ A$ und eine Ecke in $ B$ hat.

Die folgenden Abbildungen zeigen bipartite Graphen.

\includegraphics{bsp_graph3}           \includegraphics{bsp_graph4}
Dagegen ist der vollständige Graph auf 4 Ecken
\includegraphics{bsp_graph2}
nicht bipartit. Es gilt allgemein, dass vollständige Graphen mit mehr als 2 Ecken nicht bipartit sind.
(Aus: Vorkurs Mathematik)

[Verweise]

  automatisch erstellt am 26.  2. 2007