⟸ pàgina anterior ⟸
Exercici 2 (Tasca 7).
(polynomial time, exponential time, NP-completeness)

A la recerca de cliques

Una k-clica en un graf G = (V,E) és un subgraf complet d’ordre k de G, és a dir, un subgraf de k vèrtexs que conté totes les arestes possibles entre ells. Diem que G' és una clica en G si G' és una k-clica en G per a algun k. Recordeu que el problema següent és un NP-complet conegut. \mathtt{Clica}\text{: Donat un graf no dirigit $G$ i un natural $k$, determinar si $G$ conté una $k$-clica.}

Els següents són alguns problemes relacionats amb \mathtt{Clica}.

  1. Clica maximal. Una clica és maximal si no es pot estendre, és a dir, si no hi ha cap clica més gran que la contingui. Descriviu un algorisme tan eficient com pugueu que, donat un graf no dirigit G, trobi una clica maximal de G. Quin és el cost de l’algorisme?

  2. Clica màxima. Una clica és màxima si no hi ha cap altra clica que tingui més vèrtexs (una clica màxima sempre és maximal però la inclusió inversa no sempre és certa). Descriviu un algorisme tan eficient com pugueu que, donat un graf no dirigit G, trobi una clica màxima de G. Quin és el cost de l’algorisme?

  3. Clica planar. Recordeu que un graf és planar si es pot dibuixar en el pla sense creuaments d’arestes. Sigui \mathtt{Clica Planar} el problema següent: donat un graf planar no dirigit G i un natural k, té G una k-clica? Demostreu que \mathtt{Clica Planar} té un algorisme de temps polinòmic.

    Nota

    La comprovació de la planaritat es pot fer en temps lineal (en el nombre de vèrtexs). Podeu assumir l’existència d’aquests algorismes per l’exercici.

  4. Mitja clica. Sigui \mathtt{Mitja Clica} el problema següent: donat un graf no dirigit G, té G una clica amb almenys \big\lceil \frac{|V(G)|}{2} \big\rceil vèrtexs? Demostreu que \mathtt{Mitja Clica} és NP-complet.