Przejdź do zawartości

Klika (teoria grafów)

Z Wikipedii, wolnej encyklopedii

Klikapodgraf, 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 (ang. clique number) oznaczamy

Graf, którego liczba chromatyczna jest równa rozmiarowi największej kliki 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ż

[edytuj | edytuj kod]
Graf pełny K5, będąc swoim własnym podgrafem tworzy klikę rozmiaru 5

Przypisy

[edytuj | edytuj kod]
  1. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 110–111. ISBN 0-387-95014-1.