Clique (graph theory)
Clique in graph theory refers to a subset of vertices within an undirected graph such that every two distinct vertices in the clique are adjacent. This means that a clique represents a set of vertices all of which are connected to each other by edges. The concept of cliques is fundamental in the study of graph theory and has applications in various fields including social network analysis, bioinformatics, and the study of computational complexity.
Definition[edit | edit source]
A clique in an undirected graph G = (V, E) is a subset C of the vertex set V such that for every two vertices in C, there exists an edge connecting them in the edge set E. The size of the largest clique in a graph is known as the graph's clique number, denoted as ω(G).
Types of Cliques[edit | edit source]
- Maximal Clique: A clique that cannot be extended by including one more adjacent vertex, meaning it is not a subset of a larger clique.
- Maximum Clique: A clique of the largest possible size in a graph. This is a clique that has the highest number of vertices.
Finding Cliques[edit | edit source]
The problem of finding cliques, especially the maximum clique, in a graph is a well-known NP-complete problem, making it computationally challenging for large graphs. Various algorithms exist for finding cliques, including the Bron–Kerbosch algorithm for finding all maximal cliques and heuristic methods for finding large cliques in dense graphs.
Applications[edit | edit source]
Cliques have applications in many areas:
- In social network analysis, cliques can represent groups of people all of whom know each other.
- In bioinformatics, cliques can be used to identify groups of proteins that interact with each other.
- In computational complexity, the clique problem is used as a basis for proving the difficulty of other computational problems.
Clique Problem in Computational Complexity[edit | edit source]
The decision version of the clique problem, which asks whether a graph contains a clique of a certain size, is one of the Karp's 21 NP-complete problems. This highlights the intrinsic difficulty of solving this problem efficiently for large graphs.
See Also[edit | edit source]
 | This mathematics-related article is a stub. You can help WikiMD by expanding it. |
Search WikiMD
Ad.Tired of being Overweight? Try W8MD's physician weight loss program.
Semaglutide (Ozempic / Wegovy and Tirzepatide (Mounjaro / Zepbound) available.
Advertise on WikiMD
|
WikiMD's Wellness Encyclopedia |
| Let Food Be Thy Medicine Medicine Thy Food - Hippocrates |
Translate this page: - East Asian
中文,
日本,
한국어,
South Asian
हिन्दी,
தமிழ்,
తెలుగు,
Urdu,
ಕನ್ನಡ,
Southeast Asian
Indonesian,
Vietnamese,
Thai,
မြန်မာဘာသာ,
বাংলা
European
español,
Deutsch,
français,
Greek,
português do Brasil,
polski,
română,
русский,
Nederlands,
norsk,
svenska,
suomi,
Italian
Middle Eastern & African
عربى,
Turkish,
Persian,
Hebrew,
Afrikaans,
isiZulu,
Kiswahili,
Other
Bulgarian,
Hungarian,
Czech,
Swedish,
മലയാളം,
मराठी,
ਪੰਜਾਬੀ,
ગુજરાતી,
Portuguese,
Ukrainian
Medical Disclaimer: WikiMD is not a substitute for professional medical advice. The information on WikiMD is provided as an information resource only, may be incorrect, outdated or misleading, and is not to be used or relied on for any diagnostic or treatment purposes. Please consult your health care provider before making any healthcare decisions or for guidance about a specific medical condition. WikiMD expressly disclaims responsibility, and shall have no liability, for any damages, loss, injury, or liability whatsoever suffered as a result of your reliance on the information contained in this site. By visiting this site you agree to the foregoing terms and conditions, which may from time to time be changed or supplemented by WikiMD. If you do not agree to the foregoing terms and conditions, you should not enter or use this site. See full disclaimer.
Credits:Most images are courtesy of Wikimedia commons, and templates Wikipedia, licensed under CC BY SA or similar.
Contributors: Prab R. Tumpati, MD
