Vollständiger Graph - LinkFang.de





Vollständiger Graph


Ein vollständiger Graph ist ein Begriff aus der Graphentheorie und bezeichnet einen einfachen Graph, in dem jeder Knoten mit jedem anderen Knoten durch eine Kante verbunden ist. Der vollständige Graph mit [math]n[/math] Knoten ist (bis auf Isomorphie) eindeutig bestimmt und wird mit [math]K_n[/math] bezeichnet.

Ist [math]V=\{v_1,\dotsc,v_n\}[/math] die Knotenmenge des vollständigen Graphen [math]K_n[/math], so ist die Kantenmenge [math]E[/math] genau die Menge von Kanten zwischen paarweise verschiedenen Knoten [math]E=\{\{v_i,v_j\}: 1\le i\ltj\le n\}[/math].

Ein vollständiger Graph ist gleichzeitig seine maximale Clique.

Eigenschaften

Die vollständigen Graphen [math]K_1[/math] bis [math]K_4[/math] sind planar. Alle anderen vollständigen Graphen sind nach dem Satz von Kuratowski nicht planar, da sie [math]K_5[/math] als Teilgraph enthalten.

Die Anzahl der Kanten des vollständigen Graphen [math]K_n[/math] entspricht der Dreieckszahl

[math]\Delta_{n-1} = {n \choose 2}=\frac{n(n-1)}{2}[/math].

Der vollständige Graph [math]K_n[/math] ist ein [math](n-1)[/math]-regulärer Graph: jeder Knoten hat [math]n-1[/math] Nachbarn. Aufgrund dessen hat jede Knotenfärbung des Graphen [math]n[/math] Farben. Des Weiteren folgt daraus, dass die vollständigen Graphen für ungerade [math]n[/math] eulersch sind und für gerade [math]n[/math] nicht.

Vollständige Graphen sind für [math]n\gt2[/math] hamiltonsche Graphen. Der vollständige Graph [math]K_n[/math] enthält dabei [math]\tfrac{1}{2}(n-1)![/math] verschiedene Hamiltonkreise.

Verallgemeinerung

Die Idee des vollständigen Graphen lässt sich auf [math]k[/math]-partite Graphen übertragen. Diese sind vollständig, falls jeder Knoten einer Partition mit allen Knoten aller anderen Partitionen verbunden ist. Den vollständigen multipartiten Graphen mit [math]p[/math] Partitionsmengen, welche [math]n_1,\dotsc,n_p[/math] Knoten enthalten, bezeichnet man mit [math]K_{n_1, \dotsc, n_p}[/math].

Versieht man einen vollständigen Graphen mit einer Orientierung, so erhält man einen Turniergraphen.

Literatur

Weblinks


Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Vollständiger 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.