Kliko (grafeteorio)

En grafeteorio, kliko en sendirekta grafeo G estas aro de verticoj V tia ke por ĉiuj du verticoj en V ekzistas eĝo 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 nombro de verticoj en ĝi.

Grafeo kun 6 verticoj kaj 7 eĝoj. 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.

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