Yazan : Şadi Evren ŞEKER
Graf teorisinde her iki düğümü birbirine bir kenar ile bağlanmış alt graflara verilen isimdir. Örneğin aşağıdaki grafikte bir klik kırmızı çizgiler ile işaretlenmiştir. Buna göre {A,B,C,D} alt grafı bir kliktir.
Sosyal bilimlerde de aynı kelime(klik) bir toplumun en alt birimine verilen isimdir. Bunun sebebi doğrudan bağlantısı olan ve komşuluğu bulunan bireylerden oluşması olarak yorumlanabilir.
Klik yapısının tersi için bağımsız düğümler veya anti clique veya independent set terimleri kullanılır.
Sadi Bey clique problem nedir
Ah bu güncel problemlerden birisi. Mesele büyük bir graf içerisinde tamamı komşu parçalar bulmak. Örneğin yazıdaki grafı ele alalım. Burada 3 boyutundaki klikleri bulmak istiyorsanız bunlar aşağıda listelenmiştir:
ABC
BCD
ADB
ACD
BDF
Bu alt grafların (subgraph) hepsinin bütün üyelerinin diğer üyeler ile komşuluğu vardır. Yani birer clique’dir.
Büyük bir graf içerisinde bu tip kliklerin bulunması ise zaman ve hafıza kullanımı açısından tam bir problemdir. Örneğin facebook’ta birbirini arkadaş olarak ekleyenlerin graf olarak gösterilmesi mümkün (kim kiminle arkadaş şeklinde) ve bu grafta 5’li cliklerin yani 5’inin de birbirini arkadaş olarak eklediği alt grafların bulunması için çok ciddi miktarda işlem ve hafıza gerekmektedir. Bahsettiğiniz problem budur ama çözümü ile ilgili internette onlarca makale bulunuyor.
Merhaba Hocam , Vertex cover hakkında biraz açıklamada bulunabilirmisiniz ingilizce kaynaklar var ancak cok anlayamadım algoritması calısma mantıgı ve karmasıklıgı , bipartite vertex , vertex cover karmasıklıgı degişiyormu nasıl bulunuyor köseler vs ..