kordon grafiği

Olarak grafik teorisi , bir grafiktir söylemek cordal onun her ise döngü dört veya daha fazla köşelerin bir sahiptir kiriş çevriminin iki komşu olmayan köşe bağlantı bir kenar demek,. Eşdeğer bir tanım, ipsiz herhangi bir çevrimin en fazla üç köşesi olmasıdır. Olarak da adlandırılan cordal grafikler, üçgen grafikler , bir alt kümesidir mükemmel grafikler .

Ayrıca üçgenlenmiş bir grafikten bahsediyoruz .

Tanım

Bir grafik, 4 veya daha fazla uzunlukta indüklenmiş bir döngü içermiyorsa samimidir . Dört veya daha fazla uzunluktaki indüklenmiş bir döngüye delik denir . Her döngü bir üçgen olmak zorunda olduğu için "üçgenleştirilmiş grafik" terimi de kullanılır.

Karakterizasyonlar

Mükemmel eleme

Bir grafiğin mükemmel bir eleme sıralaması, grafiğin köşelerinin, herhangi bir köşe için , oluşturduğu küme ve ondan sonra bulunan komşuları bir klik oluşturacak şekilde sıralanmasıdır . Bir grafik, ancak ve ancak mükemmel bir eleme sırasına sahipse samimidir ( Fulkerson ve Gross 1965 ). $v$ $v$

Alt ağaç kavşak grafikleri

Gavril 1974 tarafından yapılan kordon grafiklerinin bir başka karakterizasyonu, ağaçları ve onların alt ağaçlarını kullanır .

Bir ağacın alt ağaçlarının bir koleksiyonundan, alt ağaç başına bir tepe noktası olan bir kesişim grafiği olan bir alt ağaç grafiğini tanımlamak mümkündür . Kenarlar, ağaçta ortak en az bir düğümü olan alt ağaçları birbirine bağlar . Gavril'in gösterdiği gibi, alt ağaç grafikleri tam olarak kordon grafikleridir. Bu temsil , grafiğin bir ağaç ayrıştırmasını oluşturur, burada grafiğin yüksekliği, grafiğin en büyük kliği eksi bire eşittir; herhangi bir grafiğin ağaç ayrışması, bu şekilde , bir kordon grafiğinin bir alt grafiği olarak temsili olarak görülebilir . $İLE$ $İLE$ $G$ $G$

Ayırıcılar

Tüm minimal ayırıcıları klik olan grafikler kordon grafikleridir.

Diğer sınıflarla ilişkiler

alt sınıflar

Aralık grafikler alt ağaç kesişme grafikleridir grafikleri yolu ; bu nedenle, kordon grafiklerinin bir alt ailesidir.

Bölünmüş grafikleri (ya da "ayrılmış", angliais bölünmüş grafikleri) tam grafikleri hem cordaux ve vardır tamamlayıcı için cordaux grafikleri. Bender, Richmond ve Wormald 1985 , bölünmüş köşelerin sayısını ve kiriş köşelerinin sayısını belirterek , sonsuza doğru eğilim gösterirken 1'e yöneldiğini gösterdi. $F (n)$ $olumsuzluk$ $C (n)$ $olumsuzluk$ $F (n) / C (n)$ $olumsuzluk$

Mükemmel trivially grafikleri tam cordaux grafikleri ve hem grafiklerdir cographs .

Aşırı sınıflar

Kordal grafikler, çift delikli (en) ve tek deliksiz grafiklerin bir alt sınıfıdır , çünkü kiriş grafikleri tanım gereği deliksiz grafiklerdir (bir delik en az 4 uzunlukta bir döngüdür).

algoritmik yönler

Kordal grafiklerin tanınması

Rose, Lueker ve Tarjan 1976 (ayrıca bkz . Habib ve diğerleri 2000 ), bir kordon grafiğinin mükemmel bir eleme sıralamasının sözlükbilimsel genişlik-ilk arama adı verilen bir algoritma kullanılarak verimli bir şekilde bulunabileceğini göstermektedir . Bu algoritma, grafiğin köşelerinin bir dizi küme şeklinde bir bölümünü tutar. Başlangıçta, bu dizi tüm köşeleri olan tek bir kümedir. Algoritma tekrar tekrar bir tepe seçecektir henüz seçilen köşe içeren sırayla genç kümesinin ve her birini ayırmak iki alt, komşuları içeren birine dizisinin içinde olmayan komşu zirveler diğer. Tüm köşeler için bu ayrım yapıldığında, dizi yalnızca bir köşe içeren kümelerden oluşur. Bu köşeler, mükemmel eleme sırasının tersi sırada bulunur. $v$ $S$ $v$ $S$

Önce genişlikte sözlükbilimsel arama ve bir sıralamanın mükemmel bir eleme sıralaması olup olmadığının test edilmesi lineer zamanda yapılabileceğinden, bir grafiğin lineer zamanda kordal olup olmadığını bilmek mümkündür.

Bir akor grafiğinin tüm sıralamalarının mükemmel bir şekilde ortadan kaldırılması , bir antimatroidin (in) temel kelimeleri olarak modellenebilir ; Chandran et al. 2003 , antimatroidlerle bu bağlantıyı, belirli bir kordon grafiğinin tüm mükemmel eleme dizilimini verimli bir şekilde listeleyen bir algoritmada kullandı.

Maksimum tıklama ve grafik boyama

Mükemmel eleme sıralamasının bir uygulaması, polinom zamanında bir kordon grafiğinin maksimum kliğini bulmaktır. Benzer problem, ancak herhangi bir grafik için, NP-complete . Genel olarak, samimi bir grafikteki maksimum kliklerin sayısı doğrusal olarak artarken, bu büyüme samimi olmayan grafiklerde üstel olabilir. Bir cordal grafiğin tüm maksimal klikler listeye, her köşe için bir klik oluşturmak için, mükemmel bir eleme sıralamasını bulmak için yeterlidir komşuları ile sonra gelen mükemmel eleme sıralamada ve her biri için teste. Cliques dolayısıyla maksimum ise oluşturulur. $v$ $v$ $v$

En büyük maksimum klik maksimum kliktir ve kordon grafikleri mükemmel grafikler olduğundan, kliğin boyutu kordon grafiğinin kromatik sayısıdır . Bir kordon grafiği mükemmel bir şekilde programlanabilir: en uygun renklendirme, açgözlü bir renklendirme algoritması (en) köşelere mükemmel eleme sıralamasının tersi sırayla uygulanarak elde edilebilir ( Maffray 2003 ).

bibliyografya

(tr) EA Bender , LB Richmond ve NC Wormald , “ Neredeyse tüm kordal grafikler bölünmüş ” , J. Austral. Matematik. Soc., Seri A , cilt. 38, n o 21985, s. 214-221, Matematik İncelemeleri bağlantısı
(tr) LS Chandran , L. Ibarra , F. Ruskey ve J. Sawada , “ Bir kordal grafiğinin mükemmel eleme sıralarını numaralandırma ve karakterize etme ” , Theoretical Computer Science , cilt. 307,2003, s. 303–317 ( DOI 10.1016 / S0304-3975 (03) 00221-4 , çevrimiçi okuyun ).
(tr) DR Fulkerson ve OA Gross , “ İnsidans matrisleri ve aralık grafikleri ” , Pacific J. Math , cilt. 15,1965, s. 835-855 ( çevrimiçi okuyun )
(tr) Fănică Gavril , “ Ağaçlardaki alt ağaçların kesişim grafikleri tam olarak kiriş grafikleridir ” , Journal of Combinatory Theory, Series B , cilt. 16,1974, s. 47–56 ( DOI 10.1016 / 0095-8956 (74) 90094-X )
.
(tr) Richard M. Karp , “Birleşimsel Problemler Arasında İndirgenebilirlik” , Raymond E. Miller ve James W. Thatcher, Complexity of Computer Computations , Plenum,1972( ISBN 978-1-4684-2003-6 , DOI 10.1007 / 978-1-4684-2001-2_9 , çevrimiçi okuyun ) , s. 85-103
(tr) Frédéric Maffray , “On the coloration of Perfect Graphics ” , Bruce A. Reed ve Cláudia L. Sales, Son Gelişmeler Algorithms and Combinatorics , Springer-Verlag, koll. Matematikte CMS Kitapları, Cilt. 11",2003( DOI 10.1007 / 0-387-22444-0_3 ) , s. 65-84.
(tr) D. Rose , George Lueker ve Robert E. Tarjan , “ Grafiklerde köşe elemenin algoritmik yönleri ” , SIAM Journal on Computing , cilt. 5,1976, s. 266–283 ( DOI 10.1137 / 0205021 ).

Notlar ve referanslar

(tr) Bu makale kısmen veya tamamen Wikipedia makalesinden alınmıştır İngilizce başlıklı " Korda grafiği " ( yazarların listesini görmek ) .

Gena Hahn, “ Üçgenleştirilmiş Grafikler ” ,2016.
Michel Habib, " Üçgen grafikler (sunu desteği) " ,2011
Gabriel Andrew Dirac , “ Rijit devre grafikleri üzerinde ”, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , cilt. 25, 1961, s. 71-76 ( DOI 10.1007 / BF02992776 , Matematik Yorumlar 0130190 ).
Genellikle LexBFS olarak kısaltılır
Bu, Karp'ın 21 NP-tamamlanmış probleminden biridir ( Karp 1972 ).

Şuna da bakın:

Dış bağlantılar

(tr) Ridder ve ark.'dan HN. 2001-2012, ISGCI (Graph Classes and Inclusions on Information System), Graphclass: chordal .