Clique (graph theory)
Adjacent subset of an undirected graph
Clique (graph theory)
In graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G {\displaystyle G} is an induced subgraph of G {\displaystyle G} that is complete. 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: the task of 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 Erdős & Szekeres (1935), the term clique comes from Luce & Perry (1949), who used complete subgraphs in social networks to model cliques of people; that is...
Read on Wikipedia · Image David Eppstein, Public domain
Open boosters, collect cards and trade them. Free to play.
Play for free