Problema della cricca: differenze tra le versioni

Versione delle 22:05, 5 apr 2014

Versione delle 22:10, 5 apr 2014

Riga 36:

Una cricca [[Elemento massimale|massimale]], talvolta chiamata massimale con inclusione, è una cricca che non è inclusa in una cricca più grande. Si noti, perciò, che ogni cricca è contenuta in una cricca massima.

Le cricche massimali possono essere molto piccole. Un grafo può contenere una cricca non massimale con molti vertici e una cricca separata di dimensione 2 che è massimale. Mentre una cricca massima (ciòcioè, più grande) è necessariamente massimale, l'inverso non vale. Ci sono alcuni tipi di grafi in cui ogni cricca è massima (i [[Grafo complemento|complementi]] dei [[Grafo ben coperto|grafi ben coperti]], che includono in particolare [[Grafo completo|grafi completi]], [[Grafo senza triangoli|grafi senza triangoli]] senza [[Vertice isolato|vertici isolati]], [[Grafo di Turán|grafi multipartiti completi]] e [[k-albero|''k''-alberi]]), ma altri grafi hanno cricche massimali che non sono massime.

Trovare una cricca massimale è immediato: partendo da una cricca arbitraria (per esempio, un singolo vertice), si fa crescere la cricca attuale un vertice alla volta iterando sui vertici rimanenti del grafo, aggiungendo un vertice se è connesso a ciascun vertice della cricca attuale e scartandolo altrimenti. Questo algoritmo funziona in [[tempo lineare]]. A causa della facilità di trovare le cricche massimali e della loro dimensione potenziale, maggiore attenzione è stata dedicata al problema algoritmico, molto più difficile, di trovare una cricca massima o altrimenti grande di quanta ne sia stata data al problema di trovare una singola cricca massima.