Kliko (grafeteorio)

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
Grafeo kun 6 verticoj kaj 7 lateroj. Verticoj 1, 2, 5 formas la solan en la grefeo klikon de amplekso 3.
K5, kompleta grafeo. Se subgrafeo aspektas tiel, la verticoj en la subgrafeo formas klikon de amplekso 5.

En grafeteorio, kliko en sendirekta grafeo G estas aro de verticoj V tia ke por ĉiuj du verticoj en V ekzistas latero konektanta ilin du. Alternative, kliko estas grafeo en kiu ĉiu vertico estas koneksa al ĉiu la alia vertico de la grafeo. Alternative, kliko estas la subgrafeo konkludita per la aro de verticoj V kiu estas kompleta grafeo. La amplekso de kliko estas la kvanto de verticoj en ĝi.

Provado ĉu estas kliko de donita amplekso en donita grafeo (la klikproblemo) estas NP-kompleta.

La kontraŭo al kliko estas sendependa aro, en la senco ke ĉiu kliko respektivas al sendependa en la komplemento de la grafeo.

La plej granda kliko en grafeo G estas de teoria graveco kaj estas skribata kiel ω(G)

Vidu ankaŭ[redakti | redakti fonton]