Bipartiter Graph - LinkFang.de





Bipartiter Graph


Ein bipartiter oder paarer Graph ist ein mathematisches Modell für Beziehungen zwischen den Elementen zweier Mengen. Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen. Des Weiteren lassen sich für bipartite Graphen viele Grapheneigenschaften mit deutlich weniger Aufwand berechnen als dies im allgemeinen Fall möglich ist.

Definitionen

Ein einfacher Graph [math]G=(V,E)[/math] (V Menge der Knoten, E Menge der Kanten) heißt bipartit oder paar, falls sich seine Knoten in zwei disjunkte Teilmengen A und B aufteilen lassen, sodass zwischen den Knoten innerhalb beider Teilmengen keine Kanten verlaufen. Das heißt für eine Kante [math]\{v,w\} \in E[/math] gilt entweder [math]v \in A[/math] und [math]w \in B[/math] oder [math]v \in B[/math] und [math]w \in A[/math]. Die Menge [math] \{A,B\} [/math] bezeichnet man dann als Bipartition des Graphen [math] G [/math] und die Mengen [math] A,B [/math] als Partitionsklassen. Vereinfacht dargestellt, ist ein bipartiter Graph ein Graph, in dem zwei Gruppen von Knoten existieren, innerhalb derer keine Knoten miteinander verbunden sind.

Der Graph [math]G[/math] heißt vollständig bipartit, falls eine Bipartition [math]\{A,B\}[/math] existiert, sodass jeder Knoten aus [math]A[/math] mit jedem Knoten aus [math]B[/math] verbunden ist. Einen solchen Graphen bezeichnet man auch als [math]K_{m,n}[/math], wobei [math]m[/math] und [math]n[/math] jeweils die Anzahl der Knoten von [math]A[/math] und [math]B[/math] sind. Ein vollständig bipartiter Graph, bei dem [math]m=1[/math] oder [math]n=1[/math] ist, heißt Sterngraph.

Eigenschaften

Mit einem einfachen Algorithmus, der auf Tiefensuche basiert, lässt sich in linearer Zeit bestimmen, ob ein Graph bipartit ist, und eine gültige Partition bzw. 2-Färbung ermitteln.

Anwendung

Verallgemeinerung

Ein k-partiter Graph ist ein Graph, dessen Knotenmenge in [math]k[/math] Partitionen unterteilt werden kann, sodass es keine Kante zwischen zwei Knoten einer Partition gibt.

Weblinks

 Commons: Bipartiter Graph  – Sammlung von Bildern, Videos und Audiodateien

Kategorien: Bipartiter Graph

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Bipartiter Graph (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.