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.

graf8.jpg

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.

Yorumlar

  1. Şadi Evren ŞEKER Article Author

    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.

  2. Abdulkadir Ok

    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 ..

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


+ dokuz = 10