Klika (teoria grafów)

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

Klika – podgraf, w którym każde dwa wierzchołki są połączone krawędzią.

Klika jest maksymalna, jeśli nie da się dodać do niej wierzchołka tak, aby razem z nią również tworzył klikę. Klika jest największa (najliczniejsza), jeśli nie ma w grafie kliki o większej liczbie wierzchołków. Rząd największej kliki grafu ${\displaystyle G}$ (ang. clique number) oznaczamy ${\displaystyle \omega (G).}$

Graf, którego liczba chromatyczna jest równa rozmiarowi największej kliki ${\displaystyle (\chi (G)=\omega (G)),}$ nazywa się grafem doskonałym (ang. perfect graph)^[1].

Stwierdzenie, czy w grafie istnieje klika o zadanym rozmiarze (problem kliki), jest jednym z klasycznych problemów NP-zupełnych. Problemem dualnym dla problemu kliki jest problem zbioru niezależnego.

Zobacz też

• graf pełny
• graf doskonały
• liczba chromatyczna

Graf pełny K₅, będąc swoim własnym podgrafem tworzy klikę rozmiaru 5

Przypisy