Klik (grafik teorisi) - Clique (graph theory)

ile bir grafik

• 23 × 1-köşe klikleri (köşeler),
• 42 × 2 köşeli klikler (kenarlar),
• 19 × 3 köşeli klikler (açık ve koyu mavi üçgenler) ve
• 2 × 4 köşeli klikler (koyu mavi alanlar).

11 açık mavi üçgen maksimum klikleri oluşturur. İki koyu mavi 4-klik hem maksimum hem de maksimumdur ve grafiğin klik sayısı 4'tür.

Olarak matematiksel bir alan grafik teorisi , bir klik ( / k l Ben bir k / veya / k l ɪ k / ) bir köşe bir alt kümesidir yönsüz grafik klik her iki farklı noktalar bitişik olduğu şekilde. Kendisine, bir grafik bir klik bir olduğunu neden alt grafiğinin bölgesinin olmasıdır tam . Klikler, çizge teorisinin temel kavramlarından biridir ve diğer birçok matematiksel problemde ve grafiklerdeki yapılarda kullanılır. Klikler ayrıca bilgisayar bilimlerinde de çalışılmıştır : bir grafikte belirli bir boyutta bir kliğin olup olmadığını bulma görevi ( klik problemi ) NP-tamamlanmıştır , ancak bu sertlik sonucuna rağmen, klikleri bulmak için birçok algoritma çalışılmıştır. ${\görüntüleme stili G}$${\görüntüleme stili G}$

Tam alt grafların incelenmesi, en azından Erdős & Szekeres (1935) tarafından Ramsey teorisinin graf-teorik yeniden formüle edilmesine kadar gitse de , klik terimi , klikleri modellemek için sosyal ağlarda tam alt grafları kullanan Luce & Perry'den (1949) gelmektedir . insanlar; yani, hepsi birbirini tanıyan insan grupları. Kliklerin bilimlerde ve özellikle biyoinformatikte birçok başka uygulaması vardır .

Tanımlar

Bir klik , bir in yönsüz grafik bir alt kümesidir köşeler , her iki farklı noktalar bitişik olduğu şekilde. Bu durumda eşdeğerdir uyarılan alt grafiğinin bölgesinin neden olduğu bir olduğu tam bir grafiktir . Bazı durumlarda, klik terimi doğrudan alt grafiğe de atıfta bulunabilir. ${\görüntüleme stili C}$ ${\görüntüleme stili G=(V,E)}$${\ Displaystyle C\subseteq V}$${\görüntüleme stili G}$${\görüntüleme stili C}$

Bir maksimum klik olan bir daha fazla bitişik köşe, daha büyük bir klik tepe grubu içindeki özel olmayan bir klik içerecek şekilde uzatılamaz bir klik olup. Bazı yazarlar, klikleri maksimum olmalarını gerektiren bir şekilde tanımlar ve maksimum olmayan tam alt grafikler için başka terminoloji kullanır.

Bir grafiğin maksimum kliği , , daha fazla köşesi olan bir klik olmayacak şekilde bir kliktir. Ayrıca, bir grafiğin klik numarası , içindeki maksimum klikteki köşe sayısıdır . ${\görüntüleme stili G}$ ${\görüntüleme stili \omega (G)}$${\görüntüleme stili G}$${\görüntüleme stili G}$

Kesişim sayısı arasında birlikte tüm kenarlarını kapsamaktadır cliques küçük sayıdır . ${\görüntüleme stili G}$${\görüntüleme stili G}$

Klik kapak sayısı bir grafik klikleri en küçük sayıdır sendika köşe kümesini kapsar grafiğinin. ${\görüntüleme stili G}$${\görüntüleme stili G}$${\görüntüleme stili V}$

Bir grafiğin maksimum klik çaprazlaması , grafiğin her maksimum kliğinin alt kümede en az bir tepe noktası içermesi özelliğine sahip bir köşe alt kümesidir.

Bir kliğin tersi bağımsız bir kümedir, şu anlamda her klik tümleyen grafiğinde bağımsız bir kümeye karşılık gelir . Klik kapak grafiğinde her köşenin dahil mümkün olduğunca az kliklerin olarak bulmakta sorun kaygılar.

İlgili bir kavram bir biclique , tam bir iki parçalı alt grafiktir . Bipartit boyutu grafik grafiğinin tüm kenarlarını kaplamak için gerekli bicliques minimum sayısıdır.

Matematik

Kliklerle ilgili matematiksel sonuçlar aşağıdakileri içerir.

• Turán teoremi , yoğun grafiklerde bir kliğin boyutu hakkında bir alt sınır verir . Bir grafiğin yeterince çok kenarı varsa, büyük bir klik içermesi gerekir. Örneğin, köşeleri ve kenarları olan her grafiğin üç köşeli bir klik içermesi gerekir.${\görüntüleme stili n}$${\displaystyle \scriptstyle \lfloor {\frac {n}{2}}\rfloor \cdot \lceil {\frac {n}{2}}\rceil }$
• Ramsey teoremi , her grafiğin veya tamamlayıcı grafiğinin , en az logaritmik köşe sayısına sahip bir klik içerdiğini belirtir.
• Moon & Moser'ın (1965) bir sonucuna göre , 3 n köşesi olan bir grafik en fazla 3 ⁿ maksimum kliğe sahip olabilir. Bu sınırı karşılayan grafikler , Turán teoreminde uç durumlar olarak ortaya çıkan Turán grafiklerinin özel bir durumu olan Ay-Moser grafikleridir K _3,3,... .
• Hadwiger'in henüz kanıtlanmamış varsayımı , bir grafikteki en büyük klik minörünün boyutunu ( Hadwiger sayısı ) kromatik numarasıyla ilişkilendirir .
• Erdos-Faber-Lovász tahmin klikler için grafik boyama ile ilgili başka kanıtlanmamış bir ifadedir.

Birkaç önemli grafik sınıfı, klikleri ile tanımlanabilir veya karakterize edilebilir:

• Bir küme grafik olan bir grafiktir bağlı bileşenler klikler bulunmaktadır.
• Bir blok grafik olan bir grafiktir biconnected bileşenler klikler bulunmaktadır.
• Bir Kordal grafik Olan köşeler mükemmel bir eleme sipariş içine sipariş edilebilir bir grafiktir, bu bir sipariş tür komşular her köşe ait v daha sonra gelecek v sıralamada bir klik oluştururlar.
• Bir cograph tüm olan kaynaklı subgraphs özelliği bir maksimum klik kesiştiği herhangi biri bir grafiğidir maksimal bağımsız grubu tek bir tepe noktası olarak.
• Bir aralık grafik olan maksimal klikler her köşe için, bu şekilde sipariş edilebilir bir grafiktir v içeren klikler v sipariş ardışık olan.
• Bir çizgi grafiğidir , kenarları her köşe kapağı cliques tam iki ait olduğu şekilde kenar ayrık klik ile örtülebilir bir grafiktir.
• Bir kusursuz bir grafik klik sayıda eşit olan bir grafiktir renk sayısı her uyarılan alt grafiği .
• Bir bölme grafik bir klik her kenarının en azından bir son nokta ihtiva ettiği bir grafiktir.
• Bir üçgen içermeyen grafik olarak köşe ve kenarlar dışında hiçbir klikler sahip bir grafiktir.

Ek olarak, diğer birçok matematiksel yapı grafiklerde klikleri içerir. Aralarında,

• Klik kompleks bir grafiğin G bir bir soyut simpleksel kompleks X ( G her klik bir simplex) G
• Bir tek yönlü grafik bir yönsüz grafik κ (olup G, bir grafikte her klik bir tepe ile) G ve tek bir tepe ile farklılık gösteren iki klikler bağlayan bir kenar. Bu, medyan grafiğine bir örnektir ve bir grafiğin klikleri üzerindeki bir medyan cebir ile ilişkilendirilir : üç A , B ve C kliğinin medyan m ( A , B , C ) , köşeleri en az ait olan kliktir. A , B ve C kliklerinden ikisi .
• Klik-toplamı ortak bir klik bunları birlikte birleşerek iki grafik bir araya getirilmesi için bir yöntemdir.
• Klik genişliği , grafiği ayrık birleşimlerden, yeniden etiketleme işlemlerinden ve verilen etiketlerle tüm köşe çiftlerini birbirine bağlayan işlemlerden oluşturmak için gereken minimum farklı köşe etiketi sayısı açısından bir grafiğin karmaşıklığı kavramıdır. Klik genişliği olan grafikler tam olarak kliklerin ayrık birlikleridir.
• Kesişim sayısı , bir grafiğin tüm grafiğin kenarlarını kaplamak için gerekli cliques minimum sayısıdır.
• Klik grafik bir grafik olan kesişim grafiği maksimal cliques.

Alt grafikleri tamamlamakla yakından ilgili kavramlar , tam grafiklerin ve tam grafik küçüklerin alt bölümleridir . Özellikle, Kuratowski'nin teoremi ve Wagner'in teoremi , sırasıyla yasaklanmış tam ve tam ikili alt bölümler ve küçükler ile düzlemsel grafikleri karakterize eder.

Bilgisayar Bilimi

Gelen bilgisayar bilimleri , klik sorun belirli bir grafikte maksimum klik veya tüm klikler, bulma hesaplama problemidir. Öyle NP-tam , biri Karp 21 NP-tam problemler . Aynı zamanda sabit parametreli inatçıdır ve tahmin edilmesi zordur . Bununla birlikte, ya üstel zamanda çalışan ( Bron-Kerbosch algoritması gibi ) ya da problemin polinom zamanında çözülebileceği düzlemsel grafikler ya da mükemmel grafikler gibi grafik aileleri için özelleşmiş , klikleri hesaplamak için birçok algoritma geliştirilmiştir .

Uygulamalar

Grafik-teorik kullanımında "klik" kelimesi , sosyal ağlardaki klikleri (birbirlerini tanıyan insan grupları) modellemek için tam alt grafikler kullanan Luce & Perry'nin (1949) çalışmasından ortaya çıktı . Aynı tanım Festinger (1949) tarafından daha az teknik terimlerin kullanıldığı bir makalede kullanılmıştır. Her iki çalışma da matrisleri kullanarak bir sosyal ağdaki klikleri ortaya çıkarmakla ilgilenir. Sosyal klikleri grafiksel olarak modellemek için devam eden çabalar için, örneğin Alba (1973) , Peay (1974) ve Doreian & Woodard (1994)'a bakınız .

Biyoinformatikten birçok farklı problem klikler kullanılarak modellenmiştir. Örneğin, Ben-Dor, Shamir & Yakhini (1999) , gen ekspresyon verilerinin kümelenmesi problemini, verileri açıklayan bir grafiği kliklerin ayrık birleşimi olarak oluşturulan bir grafiğe dönüştürmek için gereken minimum değişiklik sayısını bulma problemi olarak modelliyor ; Tanay, Sharan ve Shamir (2002) , kümelerin klikler olması gerektiği ifade verileri için benzer bir ikili kümeleme problemini tartışır . Sugihara (1984) model klikler kullanan çevresel uygunluğa olarak gıda ağları . Day & Sankoff (1986) , evrim ağaçlarının çıkarılması problemini, bu iki karakteri birleştiren mükemmel bir filogeni varsa, iki köşenin bir kenarı paylaştığı, köşeleri türün özelliklerine sahip bir grafikte maksimum klikleri bulma sorunu olarak tanımlar . Samudrala ve Moult (1998) modeli protein yapı tahmini olan köşeleri proteinin altbirimlerinden konumlarını temsil eden bir grafik klikler bulma bir sorun olarak. Spirin ve Mirny (2003) , bir protein-protein etkileşim ağındaki klikleri arayarak , birbirleriyle yakın etkileşime giren ve küme dışındaki proteinlerle çok az etkileşime sahip olan protein kümeleri buldular. Güç grafiği analizi , bu ağlardaki klikleri ve ilgili yapıları bularak karmaşık biyolojik ağları basitleştirmeye yönelik bir yöntemdir.

Gelen elektrik mühendisliği , Prihar (1956) iletişim ağları analiz etmek için klikler kullanır ve Paull ve Unger (1959) , kısmen, belirtilen mantıksal işlevleri hesaplanması için etkili bir devre tasarımı için kullanın. Klikler ayrıca otomatik test deseni oluşturmada kullanılmıştır : olası hataların uyumsuzluk grafiğindeki büyük bir klik, test setinin boyutunda bir alt sınır sağlar. Cong & Smith (1993) , bir elektronik devrenin daha küçük alt birimlere hiyerarşik bir bölümünün bulunmasında kliklerin bir uygulamasını açıklar.

Olarak kimya , Rhodes ve diğ. (2003) , bir hedef yapı ile yüksek derecede benzerliğe sahip bir kimyasal veri tabanındaki kimyasalları tanımlamak için klikler kullanır . Kuhl, Crippen & Friesen (1983) , iki kimyasalın birbirine bağlanacağı pozisyonları modellemek için klikleri kullanır.

Ayrıca bakınız

• klik oyunu

Notlar

Referanslar

Dış bağlantılar

• Weisstein, Eric W. , "Klik" , MathWorld
• Weisstein, Eric W. , "Klik Numarası" , MathWorld