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.

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 K²(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.