Vollständiger Graph

Vollständiger Graph
Die vollständigen Graphen K1 bis K5.

Ein vollständiger Graph ist ein einfacher Graph, in dem alle Knoten miteinander über eine Kante verbunden sind. Dieser Typ von Graph spielt in der Graphentheorie eine Rolle. Der vollständige Graph mit n Knoten ist (bis auf Isomorphie) eindeutig bestimmt und wird mit Kn bezeichnet.

Also: Ist V = {v1,...,vn} die Knotenmenge des Kn, so ist die Kantenmenge E genau die Menge von Kanten zwischen paarweise verschiedenen Knoten E=\{\{v_i,v_j\}: 1\le i<j\le n\}.

Inhaltsverzeichnis

Eigenschaften

Die vollständigen Graphen K1 bis K4 sind planar. Alle anderen vollständigen Graphen sind nach dem Satz von Kuratowski nicht planar, da sie K5 als Teilgraph enthalten.

Die Anzahl der Kanten des vollständigen Graphen Kn entspricht der Dreieckszahl

\Delta_{n-1} = {n \choose 2}=\frac{n(n-1)}{2}.

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

Vollständige Graphen sind für n > 2 hamiltonsche Graphen.

Verallgemeinerung

Die Idee des vollständigen Graphen lässt sich auf k-partite Graphen übertragen. Diese sind vollständig, falls jeder Knoten einer Partition mit allen Knoten aller anderen Partitionen verbunden ist.

Literatur

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Vollständiger Verband — In der Mathematik ist ein Verband eine bestimmte algebraische Struktur mit zwei Verknüpfungen bzw. eine halbgeordnete Menge mit bestimmten Eigenschaften. Inhaltsverzeichnis 1 Definition 2 Verbandsordnung 2.1 Hasse Diagramme 3 Spezielle Verbänd …   Deutsch Wikipedia

  • Bogen (Graph) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • K-regulärer Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Kubischer Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Metrischer Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Regulärer Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Schleifenfreier Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Schleifenloser Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Ungerichteter Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Eindeutig k-färbbarer Graph — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”