Maksimum Klikleri Bulma – Bilgisayar Bilimleri Ödevleri – Bilgisayar Bilimleri Ödev Hazırlatma – Bilgisayar Bilimleri Alanında Tez Yazdırma – Bilgisayar Bilimleri Ödev Yaptırma Fiyatları
Mesafeye Dayalı Klikler
Bir klik kavramını genelleştirmek için sosyal ağ teorisinin çeşitli ortamlarıyla ilgili olan bir dizi yaklaşım vardır. Bazılarını listeliyoruz. G = (V, E) yönsüz bir grafik olsun, U V’nin bir köşe altkümesi olsun ve N > 0 herhangi bir doğal sayı olsun.
u ve v köşeleri arasındaki mesafe G[U]’ya göre değil G grafiğine göre ölçüldüğünden, N-klikleri yerel olmayan özelliklere dayalıdır. Hemen bir sonuç, N > 1 için N-kliklerinin bağlanmasına gerek olmamasıdır.
Kulüpler ve klanlar yerel yapılar olsalar da (maksimumluk koşulu dışında), yoğunluktan çok mesafeleri vurguladıkları için bağlamımızda pek ilgileri yoktur. Dahası, en az iki olgu tarafından ateşlenen, mesafeye dayalı kliklere yönelik bazı eleştiriler olmuştur.
İlk olarak, birçok durumda gerçek dünya ağları genel olarak küçük bir çapa sahiptir, bu nedenle mesafe, anlamlı ağ alt yapılarını tanımlamak için oldukça kaba bir ölçüdür. İkincisi, mesafeye dayalı klikler genel olarak ne dışlama altında kapatılır ne de iç içedir.
Hesaplamalı İlkeller
Pek çok açıdan klikler, algoritmik bir bakış açısından kolayca yönetilebilen basit nesnelerdir. Çeşitli hesaplama ilkelleri için çalışma zamanı O(n + m) olan hızlı algoritmalarımız var:
1. Belirli bir U ⊆ V köşe noktası kümesinin G’de bir klik olup olmadığını belirleyin. U’nun her bir köşe çiftinin G’de bir kenar olup olmadığını test edeceğiz. çok daha az kenar, m çifti test ettikten sonra biz 2 her durumda bitiririz.
2. Belirli bir U ⊆ V kliğinin G’de maksimum olup olmadığını belirleyin. U’daki tüm köşelere bitişik olan V − U’da bir tepe noktası olup olmadığını basitçe test ediyoruz. Yine m kenarı test ettikten sonra en kötü durumda işimiz biter.
Verimli bir şekilde hesaplanabilen başka bir ilkel, bazı maksimal klikler bulmaktır. Daha sonra kullanmak üzere, bunu daha genel bir biçimde belirtiyoruz. Bir G = (V, E) grafiğinin V köşe kümesinin sıralı olduğunu varsayalım. Bir U ⊆ V kümesinin bir U’ ⊆ V kümesinden sözlüksel olarak daha küçük olduğunu ancak ve ancak hem U hem de U’da olmayan ilk tepe noktası U’ya aitse söylüyoruz.
3. Bazı U’ kliklerini içeren sözlüksel olarak en küçük maksimal kliği hesaplayın. U := U’ ayarıyla başlıyoruz, tüm v ∈ V − U’yu artan düzende yineliyoruz ve her v için U ⊆ N(v); eğer durum buysa, v tepe noktasını U’ya ekleyin. Yinelemeyi tamamladıktan sonra, U, U’ içeren maksimal bir kliktir.
Bu, O(n + m) zamanında çalışır. Algoritmik zorluklar, yalnızca belirli boyutlarda klikler veya maksimum klikler bulmakla ilgilendiğimizde ortaya çıkar. Bu problemler için, yukarıdakiyle karşılaştırılabilir çalışma sürelerine sahip hiçbir algoritma bilinmemektedir (ve muhtemelen böyle bir algoritma yoktur).
Saddle point nedir
Max min noktası Bulma
Fonksiyonun durağan noktası nasıl bulunur
Optimum nokta bulma
Koşullu ekstremum
Çok Değişkenli Fonksiyonlarda maksimum minimum Problemleri
Türev Lagrange
İki değişkenli Fonksiyonlar için Taylor formülü
Maksimum Klikleri Bulma
Maksimum klik sorununun çeşitli yönlerini tartışıyoruz. Tabii ki, eğer zamanı umursamıyorsak, maksimum büyüklükte bir kliği hesaplamak kolaydır. Bariz yaklaşım kapsamlı aramadır.
Kapsamlı bir arama algoritmasında, U ⊆ V olası tüm aday kümelerini basitçe sıralarız ve U’nun bir klik olup olmadığını inceleriz. Bulunan en büyük kliğin çıktısını alıyoruz. Basit bir tahmin, algoritmanın zaman karmaşıklığı üzerinde en kötü durum üst sınırını O(n2 · 2n) verir.
Hesaplamalı sertlik. Kapsamlı arama algoritmasını zaman miktarına göre önemli ölçüde iyileştirip iyileştiremeyeceğimiz sorunu ortaya çıkıyor. Ne yazık ki, bu muhtemelen böyle olmayacak. Hesaplamalı olarak, maksimum bir klik bulmak doğası gereği zor bir problemdir. Karşılık gelen karar problemini ele alıyoruz.
ω(G), bir G grafiğinin maksimum kliğinin boyutunu göstersin. T(n) zamanında Clique’e karar veren bir algoritmamız varsa, o zaman O(T (n) zamanında ω(G)’yi hesaplayabileceğimize dikkat edin. ) · log n) ikili arama kullanılarak. Öte yandan, ω(G)’yi hesaplamak için herhangi bir T(n) algoritması, Clique’e karar vermek için bir T(n) algoritması verir.
Böylece, Clique için bir polinom algoritmamız olsaydı, maksimum klik boyutları için bir polinom algoritmamız olurdu ve bunun tersi de geçerlidir. Bununla birlikte, Clique, NP-tamlığının tesis edildiği ilk problemler arasındaydı.
Tahmin edilen bir kümenin bir klik olup olmadığını test etmenin polinom zamanında mümkün olduğuna dikkat edin. Bu, NP’deki muhafazayı gösterir. NP-sertliğini kanıtlamak için, Satisfiability’nin Clique’e polinom-zaman dönüşümünü tarif ediyoruz.
C1,…,Ck m yan tümcelerinden oluşan birleşik normal formda bir H Boole formülü verildiğini varsayalım. H için, köşelerin yan tümceleri tarafından etiketlenen H’nin değişmezleri olduğu ve kenarların birbirini olumsuzlamayan değişmezleri bağladığı bir k-partite grafiği GH oluştururuz. Daha kesin olarak, GH = (VH,EH)’yi aşağıdaki grafik olarak tanımlayın.
Açıkça, GH grafiği H formülünün boyutunda zaman polinomunda hesaplanabilir. H’nin ancak ve ancak GH grafiğinin k boyutlu bir klik içermesi durumunda tatmin edici olduğunu gösteriyoruz.
H’nin tatmin edici olduğunu varsayalım. Daha sonra, x1,…,xn değişkenlerine, her yan tümcede en az bir hazır bilgi doğru olacak şekilde bir doğruluk ataması vardır. L1,…,Lk böyle sabit değerler olsun. O zaman, tabii ki, i ̸= j için Li ̸= ¬Lj’yi tutması gerekir. Böylece {(L1,1),…,(Lk,k)} kümesinin GH’de k boyutlu bir klik olduğunu elde ederiz.
Şimdi varsayalım ki U ⊆ VH, GH grafiğinde k büyüklüğünde bir klik olsun. GH, k-partite olduğundan, U, VH’nin her bir bölümünden tam olarak bir köşe içerir. VH kümesinin tanımıyla, U’nun tüm (L,i) ve (L’,j) köşeleri için i ̸= j olduğunda L ̸= ¬L’ elde ederiz. Dolayısıyla, değişkenlere, U’nun içerdiği tüm sabit değerlerin karşılanacağı şekilde doğruluk değerleri atayabiliriz. Bu, H formüle etmek için tatmin edici bir doğruluk ataması verir.
Bu nedenle, P = NP olmadıkça, keyfi klik boyutuna sahip Clique’i çözmek veya maksimum kliği hesaplamak için n’de çalışma süresi polinomuna sahip hiçbir algoritma yoktur. Öte yandan, G grafiğinde k büyüklüğünde bir klik olduğunu garanti etsek bile, onu polinom zamanında bulamıyoruz.
Fonksiyonun durağan noktası nasıl bulunur İki değişkenli Fonksiyonlar için Taylor formülü Koşullu ekstremum Çok Değişkenli Fonksiyonlarda maksimum minimum Problemleri Max min noktası Bulma Optimum nokta bulma Saddle point nedir Türev Lagrange