Проблем клике — разлика између измена
Садржај обрисан Садржај додат
м Стандардизација "Спољашње везе" и/или "Види још" наслова |
Нема описа измене |
||
Ред 1:
У [[рачунска теорија комплексности|рачунској теорији комплексности]], '''проблем клике''' је [[НП-комплетан проблем]] из [[теорија графова|теорије графова]]. Ово је био један од првобитних [[Карпов 21 НП-комплетан проблем|Карпових 21 НП-комплетних проблема]], које је показао НП-комплетност 1972. у раду ''Сводљивост међу комбинаторним проблемима''. Овај проблем је поменут и у Куковом раду који
[[Слика:6n-graf-clique.svg|десно|300п|мини|Граф који садржи клику величине 3.]]
Ред 9:
== Алгоритми ==
Алгоритам [[алгоритам грубе силе|грубе силе]] да се нађе клика у графу се састоји у испитивању сваког подграфа
[[Хеуристика]] се састоји у томе да се почне тако што се сваки чвор посматра као клика величине један, и да се спајају клике у све веће клике све док се више не могу извршити спајања. Две клике, -{A}- и -{B}- се могу спојити, ако је сваки чвор из клике -{A}- суседан сваком чвору из клике -{B}-. Ово захтева само линеарно време (линеарно по броју чворова), али може се десити да не пронађе велике клике, јер су два или више делова велике клике већ повезана са чворовима који нису у тој клики. Међутим, овако се проналази бар једна ''максимална клика'', што је клика која није део ниједне веће клике. Овај алгоритам је најефикасније имплементирати коришћењем [[алгоритам за налажење унија|алгоритма за налажење унија]].
| |||