Clique (grafik teorisi) - Clique (graph theory)

Bir grafik

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

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

İçinde matematiksel alanı grafik teorisi, bir klik (/ˈklbenk/ veya /ˈklɪk/) bir köşelerin alt kümesidir yönsüz grafik öyle ki klikteki her iki farklı köşe bitişiktir; yani onun indüklenmiş alt grafik dır-dir tamamlayınız. Cliques, grafik teorisinin temel kavramlarından biridir ve diğer birçok matematik probleminde ve grafikler üzerindeki yapılarda kullanılır. Cliques de çalışıldı bilgisayar Bilimi: belirli bir büyüklükte bir klik olup olmadığını bulma görevi grafik ( klik sorunu ) dır-dir NP tamamlandı, ancak bu sertlik sonucuna rağmen, klik bulmak için birçok algoritma çalışılmıştır.

Her ne kadar çalışma tamamlanmış alt grafikler en azından grafik teorik yeniden formülasyonuna geri döner Ramsey teorisi tarafından Erdős ve Szekeres (1935),^[1] dönem klik gelen Luce ve Perry (1949), içinde tam alt grafikler kullanan sosyal ağlar modellemek klikler insanların; yani, hepsi birbirini tanıyan insan grupları. Cliques'in bilimlerde ve özellikle de biyoinformatik.

Tanımlar

Bir klik, Ciçinde yönsüz grafik G = (V, E) bir alt kümesidir köşeler, C ⊆ V, öyle ki her iki farklı köşe bitişiktir. Bu, şu koşulla eşdeğerdir: indüklenmiş alt grafik nın-nin G neden oldu C bir tam grafik. Bazı durumlarda, klik terimi doğrudan alt grafiğe de atıfta bulunabilir.

Bir maksimum klik bir daha bitişik köşe ekleyerek genişletilemeyen bir kliktir, yani sadece daha büyük bir kliğin tepe kümesi içinde var olmayan bir klik. Bazı yazarlar, klikleri, maksimum olmalarını gerektiren bir şekilde tanımlar ve maksimum olmayan tam alt grafikler için diğer terminolojiyi kullanır.

Bir maksimum klik bir grafiğin G, daha fazla köşesi olan bir klik olmayacak şekilde bir kliktir. Dahası, klik numarası ω (G) bir grafiğin G bir maksimum gruptaki köşe noktalarının sayısıdır G.

kavşak numarası nın-nin G birlikte tüm kenarlarını kaplayan en küçük grup sayısıdır.G.

klik kapak numarası bir grafiğin G en küçük grup sayısı G kimin birliği köşeleri kapsıyor V grafiğin.

Bir maksimum klik enine Bir grafiğin her bir maksimum kliği, alt kümede en az bir tepe noktası içerme özelliğine sahip bir tepe alt kümesidir.^[2]

Bir kliğin zıttı bir bağımsız kümeanlamıyla, her klik bir bağımsız kümeye karşılık gelir. tamamlayıcı grafik. klik örtüsü problem, grafikteki her tepe noktasını içeren mümkün olduğunca az grup bulmakla ilgilidir.

İlgili bir kavram bir bisiklik, bir tam iki parçalı alt grafik. iki parçalı boyut Bir grafiğin tüm kenarlarını kaplamak için gereken minimum biklik sayısıdır.

Matematik

Kliklere ilişkin matematiksel sonuçlar aşağıdakileri içerir.

• Turán teoremi verir alt sınır klik büyüklüğünde yoğun grafikler.^[3] Bir grafiğin yeterince çok kenarı varsa, büyük bir grup içermesi gerekir. Örneğin, her grafik ${ displaystyle n}$ köşeler ve daha fazlası ${ displaystyle scriptstyle lfloor { frac {n} {2}} rfloor cdot lceil { frac {n} {2}} rceil}$ kenarlar üç köşeli bir klik içermelidir.
• Ramsey teoremi her grafiğin veya onun tamamlayıcı grafik en az logaritmik sayıda köşeye sahip bir klik içerir.^[4]
• Sonucuna göre Ay ve Moser (1965) 3 içeren bir grafikn köşelerde en fazla 3 olabilirⁿ maksimum klikler. Bu sınırı karşılayan grafikler Ay-Moser grafikleridir. K_3,3,...özel bir durum Turán grafikleri Turán teoreminde aşırı durumlar olarak ortaya çıkmaktadır.
• Hadwiger'in varsayımı, hala kanıtlanmamış, en büyük kliğin boyutunu ilişkilendiriyor minör bir grafikte (onun Hadwiger numarası ) onun için kromatik sayı.
• Erdős – Faber – Lovász varsayımı grafik renklendirmesini kliklerle ilişkilendiren bir başka kanıtlanmamış ifadedir.

Birkaç önemli grafik sınıfı, kliklerine göre tanımlanabilir veya karakterize edilebilir:

• Bir küme grafiği bir grafiktir bağlı bileşenler kliklerdir.
• Bir blok grafik bir grafiktir çift ​​bağlantılı bileşenler kliklerdir.
• Bir akor grafiği köşeleri mükemmel bir eleme sıralamasına göre sıralanabilen bir grafiktir, öyle bir sıralama komşular her tepe noktasının v daha sonra gelir v siparişte bir klik oluşturur.
• Bir kograf tüm indüklenmiş alt grafikleri, herhangi bir maksimal kliğin herhangi biriyle kesişme özelliğine sahip olduğu bir grafiktir. maksimum bağımsız küme tek bir tepe noktasında.
• Bir aralık grafiği maksimal klikleri her köşe için olacak şekilde sıralanabilen bir grafiktir. v, içeren klikler v sıralamada ardışıktır.
• Bir çizgi grafiği kenarları, her köşe tam olarak kapaktaki iki kliğe ait olacak şekilde kenardan ayrık klikler tarafından kapatılabilen bir grafiktir.
• Bir mükemmel grafik klik sayısının eşit olduğu bir grafiktir kromatik sayı her birinde indüklenmiş alt grafik.
• Bir bölünmüş grafik bazı grupların her kenarın en az bir uç noktasını içerdiği bir grafiktir.
• Bir üçgensiz grafik köşeleri ve kenarları dışında klik olmayan bir grafiktir.

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

• klik kompleksi bir grafiğin G bir soyut basit kompleks X(G) her grup için bir simpleks ile G
• Bir tek yönlü grafik yönsüz bir grafiktir κ (G) bir grafikteki her grup için bir tepe noktası ile G ve tek bir tepe noktası ile farklılık gösteren iki kliği birbirine bağlayan bir kenar. Bu bir örnek medyan grafik ve bir ile ilişkilidir medyan cebir bir grafiğin kliklerinde: medyan m(Bir,B,C) üç gruptan Bir, B, ve C köşeleri kliklerden en az ikisine ait olan kliktir Bir, B, ve C.^[5]
• klik toplamı iki grafiği ortak bir klik üzerinde birleştirerek birleştirmek için bir yöntemdir.
• Klik genişliği Bir grafiğin karmaşıklığı, ayrık birleşimlerden, yeniden etiketleme işlemlerinden ve verilen etiketlerle tüm köşe çiftlerini birbirine bağlayan işlemlerden grafiği oluşturmak için gereken minimum sayıda farklı köşe etiketi sayısı açısından bir grafiktir. Klik genişliğine sahip grafikler, tam olarak kliklerin ayrık birlikleridir.
• kavşak numarası Bir grafiğin tüm kenarlarını kaplamak için gereken minimum grup sayısıdır.
• klik grafiği bir grafiğin kavşak grafiği maksimal kliklerinin.

Alt grafikleri tamamlamak için yakından ilişkili kavramlar alt bölümler tam grafikler ve tamamlanmış küçük grafik. Özellikle, Kuratowski teoremi ve Wagner teoremi karakterize etmek düzlemsel grafikler yasakla tamamlandı ve tam iki parçalı sırasıyla alt bölümler ve küçükler.

Bilgisayar Bilimi

İçinde bilgisayar Bilimi, klik sorunu belirli bir grafikte maksimum birliği veya tüm grupları bulmanın hesaplama problemidir. Bu NP tamamlandı, biri Karp'ın 21 NP-tam problemi.^[6] Aynı zamanda sabit parametreli inatçı, ve yaklaşması zor. Yine de birçok algoritmalar bilgi işlem kümeleri geliştirildi. üstel zaman (benzeri Bron – Kerbosch algoritması ) veya grafik aileleri için uzmanlaşmıştır. düzlemsel grafikler veya mükemmel grafikler problemin çözülebileceği polinom zamanı.

Başvurular

Grafik-teorik kullanımında "klik" kelimesi, Luce ve Perry (1949), modellemek için tüm alt grafikleri kullanan klikler (birbirini tanıyan insan grupları) sosyal ağlar. Aynı tanım, Festinger (1949) daha az teknik terimler kullanan bir makalede. Her iki çalışma da matrisleri kullanarak bir sosyal ağdaki klikleri ortaya çıkarmayı ele alıyor. Teorik olarak sosyal klikleri modellemeye yönelik devam eden çabalar için bkz. Alba (1973), Peay (1974), ve Doreian ve Woodard (1994).

Birçok farklı problem biyoinformatik klikler kullanılarak modellenmiştir. Örneğin, Ben-Dor, Shamir ve Yakhini (1999) Kümeleme problemini modellemek gen ifadesi verileri tanımlayan bir grafiği, kliklerin ayrık birleşimi olarak oluşturulmuş bir grafiğe dönüştürmek için gereken minimum değişiklik sayısını bulmaktan biri olarak veriler; Tanay, Sharan ve Shamir (2002) benzerini tartış çift ​​küme oluşturma Kümelerin klik olması gereken ifade verileri için problem. Sugihara (1984) modellemek için klikler kullanır Ekolojik nişler içinde besin ağları. Gün ve Sankoff (1986) çıkarım problemini tarif etmek evrimsel ağaçlar Türlerin köşeleri özelliklerine sahip olan bir grafikte, iki köşenin bir kenar varsa bir kenarı paylaştığı bir grafikte maksimum klikler bulmaktan biri olarak mükemmel soyoluş bu iki karakteri birleştirerek. Samudrala ve Moult (1998) model protein yapısı tahmini Köşeleri proteinin alt birimlerinin konumlarını temsil eden bir grafikte klikler bulma sorunu olarak. Ve bir klik arayarak protein-protein etkileşimi ağ, Spirin ve Mirny (2003) birbirleriyle yakın etkileşime giren ve kümenin dışındaki proteinlerle çok az etkileşimi olan protein kümeleri buldu. Güç grafiği analizi bu ağlarda klikler ve ilgili yapıları bularak karmaşık biyolojik ağları basitleştirmek için bir yöntemdir.

İçinde elektrik Mühendisliği, Prihar (1956) iletişim ağlarını analiz etmek için klikler kullanır ve Paull ve Unger (1959) kısmen belirtilen Boole işlevlerini hesaplamak için verimli devreler tasarlamak için bunları kullanın. Klikler de kullanılmıştır otomatik test modeli oluşturma: Olası hataların bir uyumsuzluk grafiğindeki büyük bir klik, bir test setinin boyutunda daha düşük bir sınır sağlar.^[7] Cong ve Smith (1993) Bir elektronik devrenin hiyerarşik bir bölümünü daha küçük alt birimlere bulmada kliklerin bir uygulamasını açıklar.

İçinde kimya, Rhodes vd. (2003) kimyasalları tanımlamak için klikler kullanın kimyasal veritabanı bir hedef yapı ile yüksek derecede benzerliğe sahip. Kuhl, Crippen ve Friesen (1983) iki kimyasalın birbirine bağlanacağı pozisyonları modellemek için klikler kullanın.

Ayrıca bakınız

• Clique oyunu

Notlar

Referanslar

Dış bağlantılar

• Weisstein, Eric W. "Clique". MathWorld.
• Weisstein, Eric W. "Klique Numarası". MathWorld.