Kliko (grafeoteorio)

dekstra|eta|200px|K5, kompleta grafeo. Se subgrafeo aspektas tiel, la verticoj en la subgrafeo formas klikon de amplekso 5.

En grafeoteorio, 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.

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ŭ 
 Maksimuma komuna subgrafea izomorfia problemo
 Maksimuma kliko
 Hipergrafeo
 Hipereĝo

Kategorio:Grafeteorio
Kategorio:Komputa komplikeco