Clique Graph
(Redirected from clique graph)
Jump to navigation
Jump to search
A Clique Graph is a dense subgraph with every graph node connected to every other graph node (where the clique relation is true)
- AKA: Clique Subgraph.
- Context:
- It can range from being a Small Clique to being a Large Clique.
- …
- Example(s):
- a Maximal Clique.
- a Maximum Clique.
- …
- Counter-Example(s):
- See: Biclique, Neighboring Clique, Root Clique, Clique Identification Task.
References
2013
- http://en.wikipedia.org/wiki/Clique_%28graph_theory%29
- In the mathematical area of graph theory, a clique ( /ˈkliːk/ or /ˈklɪk/) in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result many algorithms for finding cliques have been studied.
Although the study of complete subgraphs goes back at least to the graph-theoretic reformulation of Ramsey theory by Template:Harvtxt,[1] the term "clique" comes from Template:Harvtxt, who used complete subgraphs in social networks to model cliques of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in bioinformatics.
- In the mathematical area of graph theory, a clique ( /ˈkliːk/ or /ˈklɪk/) in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result many algorithms for finding cliques have been studied.
- http://en.wikipedia.org/wiki/Clique_%28graph_theory%29#Definitions
- A clique in an undirected graph G = (V, E) is a subset of the vertex set C ⊆ V, such that for every two vertices in C, there exists an edge connecting the two. This is equivalent to saying that the subgraph induced by C is complete (in some cases, the term clique may also refer to the subgraph).
- ↑ The earlier work by Template:Harvtxt characterizing planar graphs by forbidden complete and complete bipartite subgraphs was originally phrased in topological rather than graph-theoretic terms.