Cliquen-Graph

Cliquen-Graph

Clique-Graphen sind Objekte der Graphentheorie. Das Finden einer Clique einer bestimmten Größe in einem Graphen ist ein NP-vollständiges Problem und somit auch in der Informationstechnik ein relevantes Forschungs- und Anwendungsgebiet. Der Begriff Clique geht dabei auf Luce Perry[1] zurück, der den Begriff zuerst für soziale Netze verwendete, in denen eine Gruppe, in der jeder jeden kennt, als ebensolche bezeichnet wird.

Inhaltsverzeichnis

Definition

Clique-Graphen sind für schleifenlose und ungerichtete Graphen definiert. Ein Graph ist eine Clique, wenn alle Knoten paarweise miteinander verbunden sind (Vollständiger Graph) und es keinen Knoten außerhalb der Clique gibt, der mit allen Knoten der Clique verbunden ist. Der Cliquen-Graph K(G) eines Graphen G ist der Graph, der sich ergibt, wenn alle Cliquen jeweils einem Knoten zugeordnet und zwei Knoten verbunden werden, wenn die zugehörigen Cliquen in G gemeinsame Knoten haben. Iterierte Clique-Graphen werden folgendermaßen definiert:

K^n(G) = K(K^{n-1}(G)),~\text{wenn}~n~>~0

K^n(G) = G,~\text{wenn}~n~=~0

Zwei direkt miteinander verbundene Knoten stellen dabei eine Clique der Größe 2 dar.

Cliquenverhalten

Wenn man Cliquen Graphen beliebig hoher Iteration betrachtet gibt es zwei mögliche Verhaltensweisen. Periodisches Cliquenverhalten tritt auf, wenn es einen Graphen gibt, der einem Graphen entspricht, der in der Abfolge von Cliquen-Graphen schon früher aufgetreten ist. Also:

K^i(G) = K^j(G),~i \neq j

Die zweite Möglichkeit ist, dass der Graph Cliquendivergent ist. Das ist der Fall, wenn es für die Anzahl an Knoten, aus denen ein beliebiger Graph aus der Abfolge iterierter Cliquen-Graphen besteht, keine obere Schranke gibt.

\lim_{i \to \infty} |V(K^i(G))| = \infty

V(G) ist die Menge der Knoten des Graphen G.

Zusätzlich wird der Fall unterschieden, dass die iterierten Cliquen-Graphen ab einer bestimmten Iteration gleich dem Einvertexgraph sind, ein Graph der genau aus einem Knoten besteht. In diesem Fall bezeichnet man das Cliquenverhalten als konvergent.

Die Clique-Helly-Eigenschaft

Der Hajos-Graph. Er ist der kleinste Graph, der nicht die Clique-Helly-Eigenschaft besitzt.

Ein Graph hat die Clique-Helly-Eigenschaft, wenn die Familie seiner Cliquen die Helly-Eigenschaft besitzt. Graphen mit der Clique-Helly-Eigenschaft weisen in Zusammenhang mit Clique-Graphen einige Interessante Eigenschaften auf.

Die Cliquen-Graphen von Graphen mit der Clique-Helly-Eigenschaft besitzen selbst die Clique-Helly-Eigenschaft.

Zu jeden Graph H mit der Clique-Helly-Eigenschaft gibt es einen Graphen G, sodass der Clique-Graph von G isomorph zu H ist.

Der Clique-Graph der zweiten Iteration K2(G) eines Graphen G mit der Clique-Helly-Eigenschaft ist ein induzierter Subgraph von G. Ein Graph mit der Clique-Helly-Eigenschaft ist also niemals cliquendivergent und seine Periode beträgt höchstens zwei.

Literatur

J. L. Szwarcfiter: A Survey on Clique Graphs. In: Recent Advances in Algorithmsand Combinatorics. Springer, New York 2003, S. 109-136.

F. Escalante: Über iterierte Clique-Graphen. In: Abhandlungen des Mathematischen Seminars der Universität Hamburg. Band 39. Springer, Berlin / Heidelberg 1973, S. 58-68.

Quellen

  1. Luce, R. Duncan; Perry, Albert D. (1949), "A method of matrix analysis of group structure", Psychometrika 14 (2): 95–116, doi:10.1007/BF02289146, PMID 18152948.

Wikimedia Foundation.

Игры ⚽ Нужен реферат?

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

  • Knotenüberdeckungen, Cliquen und stabile Mengen — sind Begriffe der Graphentheorie und bezeichnen spezielle Teilmengen von Knoten in Graphen. Das Finden von kleinsten Knotenüberdeckungen und größten Cliquen bzw. stabilen Mengen gilt als algorithmisch schwierig (NP vollständig). Da diese Probleme …   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

  • Erdős-Rényi-Graph — Ein Zufallsgraph bezeichnet einen Graphen, bei dem die Kanten zufällig erzeugt werden. Häufig eingesetzte Modelle zufälliger Graphen sind: Erdős Rényi Graph: G(n,p) mit einer natürlichen Zahl und einer Wahrscheinlichkeit bezeichnet die Menge… …   Deutsch Wikipedia

Share the article and excerpts

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