Statements (33)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
graph
|
| gptkbp:defines |
A subset of vertices of an undirected graph such that every two distinct vertices are adjacent.
|
| gptkbp:field |
gptkb:mathematics
graph theory |
| https://www.w3.org/2000/01/rdf-schema#label |
clique (graph theory)
|
| gptkbp:property |
A maximum clique is a clique of the largest possible size in a given graph.
Every graph with n vertices has a clique of size at least 1 and at most n. The clique number of a graph is the size of its largest clique. Cliques are related to the Bron–Kerbosch algorithm. The clique problem is a classic NP-complete problem. A clique of size k is called a k-clique. Cliques are related to Ramsey theory. Cliques are related to Turán's theorem. Cliques are related to chordal graphs. Cliques are related to graph coloring. Cliques are related to perfect graphs. Cliques are used in chemistry. Cliques are used in coding theory. Cliques are used in computational biology. Cliques are used in computer vision. Cliques are used in social network analysis. Every complete graph is a clique. Finding the largest clique is NP-complete. A maximal clique is a clique that cannot be extended by including one more adjacent vertex. |
| gptkbp:relatedTo |
gptkb:maximum_clique_problem
gptkb:clique_cover graph independent set clique complex clique graph clique number |
| gptkbp:bfsParent |
gptkb:Clique_problem
|
| gptkbp:bfsLayer |
6
|