Was ist eine Clique in der Graphentheorie?
What is a clique in graph theory?
In graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent.
In der Graphentheorie ist eine Clique eine Teilmenge von Knoten in einem ungerichteten Graphen, bei der jeweils zwei verschiedene Knoten in der Clique benachbart sind.
closed_qa
Im mathematischen Bereich der Graphentheorie ist eine Clique eine Teilmenge von Knoten eines ungerichteten Graphen, die so beschaffen ist, dass jeweils zwei verschiedene Knoten in der Clique benachbart sind. Das heißt, eine Clique eines Graphen G ist ein induzierter Untergraph von G, der vollständig ist. Cliquen sind eines der grundlegenden Konzepte der Graphentheorie und werden in vielen anderen mathematischen Problemen und Konstruktionen auf Graphen verwendet. Cliquen wurden auch in der Informatik untersucht: Die Aufgabe, herauszufinden, ob es in einem Graphen eine Clique mit einer bestimmten Größe gibt (das Cliquenproblem), ist NP-komplett, aber trotz dieses Schwierigkeitsergebnisses wurden viele Algorithmen zum Finden von Cliquen untersucht.

Obwohl die Untersuchung vollständiger Teilgraphen mindestens auf die graphentheoretische Neuformulierung der Ramsey-Theorie durch Erdős & Szekeres (1935) zurückgeht, stammt der Begriff Clique von Luce & Perry (1949), die vollständige Teilgraphen in sozialen Netzwerken verwendeten, um Cliquen von Personen zu modellieren, d. h. Gruppen von Personen, die sich alle gegenseitig kennen. Cliquen haben viele weitere Anwendungen in den Wissenschaften und insbesondere in der Bioinformatik.
de