Kordal tamamlama - Chordal completion
Olarak grafik teorisi , matematik bir dalı, bir kiriş tamamlanması belirli bir bölgesinin yönsüz grafik G a, kiriş grafik olan aynı tepe grubu üzerinde, G , bir alt grafiği olarak. Bir minimum kiriş tamamlama bir kenar çıkarılmasıyla oluşan herhangi bir grafik artık kiriş tamamlanması olacağını bir kiriş tamamlama şekildedir. Bir az kiriş tamamlanması mümkün olduğunca az kenarları gibi bir kiriş tamamlanmasıdır.
Elde edilen kiriş grafiğindeki maksimum kliğin boyutunu en aza indiren farklı bir kiriş tamamlama türü , G'nin ağaç genişliğini tanımlamak için kullanılabilir . Kiriş tamamlama ayrıca içermeyen grafikler de dahil olmak üzere birkaç diğer grafik sınıfları karakterize etmek için kullanılabilir pençe içermeyen AT içermeyen grafikler ve cographs .
Minimum akor tamamlama, karmaşıklığı 1979 tarihli Computers and Intractability kitabında açık olarak listelenen on iki hesaplama probleminden biriydi . Kordal tamamlama uygulamaları, seyrek simetrik matrisler üzerinde Gauss eliminasyonu gerçekleştirirken dolguyu en aza indirme problemini modellemeyi ve filogenetik ağaçları yeniden yapılandırmayı içerir .
Bir grafiğin akort tamamlamalarına bazen nirengi denir, ancak bu terim, maksimal düzlemsel grafiklere de atıfta bulunabileceğinden, grafik teorisi bağlamında bile belirsizdir .
İlgili grafik aileleri
Bir grafik G, bir bir AT içermeyen grafik ve minimum kiriş tamamlama tümü yalnızca eğer aralık grafikleri . G , pençesiz AT'siz bir grafiktir, ancak ve ancak tüm minimum kiriş tamamlamaları uygun aralık grafikleriyse. Ve G , ancak ve ancak tüm minimal kiriş tamamlamalarının önemsiz derecede mükemmel grafikler olması durumunda bir kopyadır .
Bir grafik G sahip treewidth en k ancak ve ancak G, en az bir kiriş tamamlama vardır en klik boyutu en az bir K + 1 . En fazla k yol genişliğine sahiptir , ancak ve ancak G'nin en az bir akor tamamlaması varsa, bu en fazla k +1'de maksimum klik boyutuna sahip bir aralık grafiğidir . En fazla k bant genişliğine sahiptir , ancak ve ancak G'nin en az bir akor tamamlaması varsa, bu en fazla k +1'de maksimum klik boyutuna sahip uygun bir aralık grafiğidir . Ve sahip olduğu ağaç derinlik k en maksimum klik boyuta sahip bir trivially mükemmel grafiktir en az bir kiriş tamamlama vardır ancak ve ancak k .
Uygulamalar
Bilgisayarlar ve İntractability'de açıklanan kordal tamamlamanın orijinal uygulaması, seyrek matrisler için Gauss eliminasyonunu içerir . Gauss eleme işlemi sırasında, başlangıçta sıfır olan ancak daha sonra sıfır olmayan matrisin dolgu katsayılarını en aza indirmek istenir, çünkü bu katsayıların değerlerini hesaplama ihtiyacı algoritmayı yavaşlatır. Seyrek simetrik bir matriste sıfır olmayanların modeli, yönsüz bir grafikle tanımlanabilir (matrisi komşuluk matrisi olarak içerir ); doldurulmuş matristeki sıfır olmayan desen her zaman bir kiriş grafiğidir, herhangi bir minimum kiriş tamamlama bu şekilde bir dolgu desenine karşılık gelir. Bir grafiğin kiriş tamamlaması verilirse, bu doldurma modelini elde etmek için Gauss eliminasyonunun gerçekleştirileceği bir dizi adım, sonuçtaki kiriş grafiğinin bir eleme sıralaması hesaplanarak bulunabilir. Bu şekilde, minimum doldurma problemi, minimum akor tamamlama problemine eşdeğer olarak görülebilir. Bu uygulamada, iki boyutlu sonlu eleman sistemlerinin çözümünde düzlemsel grafikler ortaya çıkabilir; Bu izler , düzlemsel ayırıcı teoremi her düzlemsel grafiği hep N köşe en sahip bir kiriş tamamlama vardır O ( n log n ) kenarları.
Başka bir uygulama filogeniden gelir, örneğin genetik mutasyonlara maruz kalan organizmaların ağaçları veya başka bir konudan kopyalanan eski el yazmalarının ağaçları gibi evrim ağaçlarının yeniden yapılandırılması sorunu. Her bir genetik mutasyonun veya yazım hatasının yalnızca bir kez meydana geldiği varsayılırsa, mükemmel bir filogeni , belirli bir özelliğe sahip türlerin veya el yazmalarının her zaman bağlantılı bir alt ağaç oluşturduğu bir ağaç elde edilir. Şöyle Buneman (1974) tarif etmektedir, mükemmel filojenezinin varlığı kiriş tamamlama sorun olarak modellenebilir. Biri , köşelerin nitelik değerleri (bir türün veya el yazmasının bazı özellikleri için belirli seçimler) olduğu ve kenarların en az bir tür tarafından paylaşılan nitelik değerleri çiftlerini temsil ettiği bir G "örtüşen grafiği" çizilir. Grafiğin köşeleri, her bir öznitelik değerinin geldiği özelliklerin kimlikleriyle renklendirilebilir , böylece toplam renk sayısı, filogeniyi türetmek için kullanılan özelliklerin sayısına eşit olur. O zaman mükemmel bir filogeni, ancak ve ancak G'nin renklendirmeye saygı gösteren bir kordal tamamlamaya sahip olması durumunda var olur .
hesaplama karmaşıklığı
1979 tarihli Computers and Intractability kitabında açık bir problem olarak listelenmesine rağmen , minimum akor tamamlama probleminin ( minimum doldurma problemi olarak da adlandırılır) hesaplama karmaşıklığı hızla çözüldü: Yannakakis (1981) bunun NP-tamamlanmış olduğunu gösterdi . Minimum kiriş tamamlama , bir G grafiğine k kenar eklerse , polinom zamanında en fazla 8 k 2 eklenmiş kenar kullanarak bir kiriş tamamlama bulmak mümkündür . Toplanacak en uygun k kenar kümesini bulma sorunu , grafik boyutunda zaman polinomu ve k cinsinden alt-üssel olarak sabit parametreli izlenebilir bir algoritma ile de çözülebilir .
Treewidth (en az klik bir kiriş tamamlanma boyutu) ve pathwidth ve ağaç derinlemesine dahil olmak üzere ilgili parametreleri hesaplamak için NP-tam ve de vardır (p = NP sürece) optimum değerlerinin sabit bir faktörü dahilinde polinom zamanda yaklaşık olarak edilemez ; bununla birlikte, logaritmik yaklaşım oranlarına sahip yaklaşım algoritmaları onlar için bilinmektedir.
Hem minimum doldurma hem de ağaç genişliği sorunları üstel zamanda çözülebilir . Daha kesin olarak, bir n- köşe grafiği için zaman O'dur (1.9601 n ) .