Clique (graph theory)

The articles clique graph and clique (graph theory) overlap thematically. Help me to better differentiate or merge the articles (→ instructions ) . To do this, take part in the relevant redundancy discussion . Please remove this module only after the redundancy has been completely processed and do not forget to include the relevant entry on the redundancy discussion page{{ Done | 1 = ~~~~}}to mark. Tavin ( discussion ) 5:56 p.m. , Jan. 10, 2018 (CET)

In graph theory, a clique describes a subset of nodes in an undirected graph in which each pair of nodes is connected by an edge. To decide whether a graph contains a clique of a certain minimum size is called a clique problem and, like finding the largest cliques, is algorithmically difficult ( NP-complete ).

Definitions

A graph with a clique of size 3.

Let be an undirected graph without multiple edges and a subset of . A clique is a subset of that induces a complete subgraph . If there is a clique, then for the subgraph , where all edges out contain that connect two nodes in , that any two different nodes and out are connected to each other by an edge. ${\ displaystyle G = (V, E)}$ ${\ displaystyle U}$ ${\ displaystyle V}$ ${\ displaystyle U}$ ${\ displaystyle V}$ ${\ displaystyle U}$ ${\ displaystyle H = (U, F)}$ ${\ displaystyle F}$ ${\ displaystyle E}$ ${\ displaystyle U}$ ${\ displaystyle v}$ ${\ displaystyle w}$ ${\ displaystyle U}$

A clique of is called a maximum if you cannot add another node from to , so that together with is a clique. If there is no clique in any clique that contains more elements than it is called the largest clique . The number of elements in a largest clique is called the clique number . ${\ displaystyle U}$ ${\ displaystyle G}$ ${\ displaystyle v}$ ${\ displaystyle V}$ ${\ displaystyle U}$ ${\ displaystyle U}$ ${\ displaystyle v}$ ${\ displaystyle G}$ ${\ displaystyle U}$ ${\ displaystyle U}$

A partition of the set of nodes into pairwise disjoint cliques is called clique coverage of the size . The clique graph of a graph is derived from the cliques . ${\ displaystyle G}$ ${\ displaystyle k}$ ${\ displaystyle V (G)}$ ${\ displaystyle k}$ ${\ displaystyle V_ {1}, V_ {2}, \ ldots, V_ {k}}$

Directed graphs or graphs with multiple edges are not the subject of such considerations, since the direction or multiplicity of the edges is not important.

properties

For every clique of a graph there is a stable set in the complement graph .

Problems and complexities

The decision problem for a graph and a natural number to decide whether a clique contains at least the size is called the clique problem (CLIQUE) . The associated optimization problem asks for the number of cliques in a graph. The associated search problem asks for a largest clique. These three problems are polynomially equivalent. ${\ displaystyle G}$ ${\ displaystyle k}$ ${\ displaystyle G}$ ${\ displaystyle k}$

The clique problem is one of Karp's 21 NP-complete problems . The associated optimization and search problems are NP-equivalent . To prove the NP severity of the clique problem, there is a reduction from 3-SAT to the clique problem.

A largest clique, however, can be calculated in polynomial time if the complement graph is bipartite . In fact, it is even more true that the number of cliques in perfect graphs can be calculated in polynomial time. Since the chromatic number and the clique number are identical in such graphs, their chromatic number can also be calculated in polynomial time. A simple greedy algorithm can be used to calculate a maximum clique .

software

Algorithms for finding and manipulating cliques are in the free Python - Library NetworkX implemented.

Individual evidence

^ Algorithms - Clique. In: NetworkX 2.2 documentation. Retrieved October 25, 2018 .

[1] Algorithms - Clique. In: NetworkX 2.2 documentation. Retrieved October 25, 2018 .