Dejenerasyon (grafik teorisi) - Degeneracy (graph theory)

2-dejenere bir grafik: her köşenin solunda en fazla iki komşusu vardır, bu nedenle herhangi bir alt grafiğin en sağ köşesinin en fazla iki derecesi vardır. 2 çekirdekli, ikiden küçük dereceli köşeleri tekrar tekrar sildikten sonra kalan alt grafik gölgelidir.

Olarak grafik teorisi , bir k Dejenere grafik bir olan yönsüz grafik her alt grafiğinin bir tepe noktasını sahip olduğu derecesi en fazla k :, bazı alt grafiğinin dokunur tepe k ya da alt grafiğini kenarlarının az. Dejenerasyon , grafiğin en küçük değeri olan k o olduğu k Dejenere. Bir grafiğin yozlaşması, ne kadar seyrek olduğunun bir ölçüsüdür ve bir grafiğin ağaçsılığı gibi diğer seyreklik ölçülerinin sabit bir faktörü içindedir .

Dejenerasyon aynı zamanda k- çekirdek sayısı , genişlik ve bağlantı olarak da bilinir ve esasen renklendirme numarası veya Szekeres-Wilf numarası ile aynıdır ( Szekeres ve Wilf'ten  ( 1968 ) sonra adlandırılır ). k Dejenere grafikler de adı olmuştur k -inductive grafikleri . Bir grafiğin dejenerasyonu, minimum dereceli köşeleri tekrar tekrar ortadan kaldıran bir algoritma ile doğrusal zamanda hesaplanabilir . Bağlı bileşenler daha az derecede tüm köşe sonra kalan k denir kaldırılmış k -cores grafiğin bir grafik dejeneriliğini en büyük değerdir k bir yer alır, öyle ki k Çekirdekli.

Örnekler

Her sonlu ormanın ya yalıtılmış bir tepe noktası (kenarsız olay) ya da bir yaprak tepe noktası (tam olarak bir kenar olayı) vardır; bu nedenle, ağaçlar ve ormanlar 1-dejenere grafiklerdir. Her 1-dejenere grafik bir ormandır.

Her sonlu düzlemsel grafiğin köşe noktası beş veya daha az derecedir; bu nedenle, her düzlemsel grafik 5-dejeneredir ve herhangi bir düzlemsel grafiğin dejenerasyonu en fazla beştir. Benzer şekilde, her dış düzlemsel grafiğin en fazla iki dejenerasyonu vardır ve Apollon ağlarının dejenerasyonu üçtür.

Barabási-Albert modeli oluşturmak için rastgele kazan taşsız ağları bir sayı parametreli m grafik eklenen her köşe sahip olacak şekilde m daha önce ilave köşe. Bu şekilde oluşturulan bir ağın herhangi bir alt grafiğinin en fazla m (alt grafiğin grafiğe eklenen son köşesi) dereceli bir tepe noktasına sahip olduğu ve Barabási-Albert ağlarının otomatik olarak m- dejenere olduğu izler.

Her k -düzenli grafiğin tam olarak k dejenerasyonu vardır  . Daha güçlü bir şekilde, bir grafiğin yozlaşması, ancak ve ancak grafiğin bağlı bileşenlerinden en az birinin maksimum derecede düzenli olması durumunda maksimum köşe derecesine eşittir . Diğer tüm grafikler için dejenerasyon, maksimum dereceden kesinlikle daha azdır.

Tanımlar ve denklikler

Bir G grafiğinin renk numarası, Erdős & Hajnal (1966) tarafından, her bir köşenin sıralamada daha önceki κ komşularından daha azına sahip olduğu G'nin köşelerinin bir sıralamasının olduğu en az κ olarak tanımlandı . Köşeleri renklendirmek için gereken minimum renk sayısı olan G'nin kromatik sayısından ayırt edilmelidir , böylece iki bitişik köşe aynı renge sahip olmaz; renk numarasını belirleyen sıralama, G'nin köşelerini renklendirme numarasıyla renklendirmek için bir sıralama sağlar, ancak genel olarak kromatik sayı daha küçük olabilir.

Bir grafik dejenereliği G tarafından tanımlanan Lick & White (1970) en az olarak k , her şekilde uyarılan alt grafiğinin bölgesinin G bir tepe ihtiva k veya daha az komşu. Uyarılmış alt graflar yerine keyfi alt graflara izin verilirse tanım aynı olacaktır, çünkü indüklenmemiş bir alt graf sadece aynı tepe kümesi tarafından indüklenen alt graftaki tepe derecelerine eşit veya daha küçük tepe derecelerine sahip olabilir.

Renklendirme sayısı ve yozlaşmanın iki kavramı eşdeğerdir: herhangi bir sonlu grafikte yozlaşma, renklendirme sayısından sadece bir eksiktir. İçin, bir grafiktir, her alt grafiğinin sonra sayısı k boyama ile bir sıralama varsa H ait köşe H ve sipariş en k de sahip en son olan - 1 komşu H . Diğer bir yönde, G, bir k Dejenere, sayı boyama daha sonra bir sipariş k  + 1 arka arkaya bir köşe bulma ile elde edilebilir v en ile k çıkarılması, komşu v Grafikten kalan köşe sipariş ilave edilmesi ve v siparişin sonuna kadar.

Üçüncü bir eşdeğer formülasyon ki G, bir k Dejenere (veya en fazla sayıda boyama olan k  + 1) ise ve kenarları sadece G oluşturmak üzere yönlendirilebilir yönlendirilmiş asiklik grafiği ile outdegree en k . Böyle bir yönlendirme, bir renk numarası sıralamasında her bir kenarı iki uç noktasından öncekine doğru yönlendirerek oluşturulabilir. Diğer yönde, k dereceli bir oryantasyon verilirse,  elde edilen yönlendirilmiş asiklik grafiğin topolojik sıralaması olarak k + 1 renk numaralı bir sıralama elde edilebilir .

k -Çekirdekler

Bir k bir grafik -çekirdek G a, maksimal bir bağlı alt grafiğinin G , tüm noktalar, en azından derecesine sahip olan k . Aynı şekilde, bu biri bağlı bileşenlerin alt grafiği ve G , art arda en az derecede tüm köşe silinmesi ile oluşturulan k . Boş olmayan ise k -çekirdek var, o zaman, açıkça, G en az dejenerelik sahiptir k ve dejenerelik G büyüğüdür k kendisi için G bir sahiptir k -CORE.

Bir köşe , bir -çekirdeğe aitse, ancak herhangi bir -çekirdeğe ait değilse, öze sahiptir. ${\görüntüleme stili u}$ ${\görüntüleme stili c}$${\görüntüleme stili c}$${\görüntüleme stili (c+1)}$

Bir k- çekirdek kavramı, sosyal ağların kümelenme yapısını incelemek ve rastgele grafiklerin evrimini tanımlamak için tanıtıldı . Ayrıca biyoinformatik , ağ görselleştirme , İnternet yapısı, ekonomik krizlerin yayılması, etkili yayıcıların belirlenmesi, beyin korteks yapısı veya ekolojideki ağların esnekliğinde uygulanmıştır . Ağırlıklı ağlardaki k çekirdekli yapıların uzantıları da geliştirilmiştir. Ana kavramları, önemli algoritmik teknikleri ve ayrıca bazı uygulama alanlarını kapsayan konuyla ilgili bir araştırma Malliaros ve diğerlerinde bulunabilir. (2019) .

Önyükleme sızıntısı , salgın bir model olarak ve dağıtılmış bilgi işlem için hata toleransı için bir model olarak incelenen rastgele bir süreçtir . Bir kafesten veya başka bir boşluktan rastgele bir aktif hücre alt kümesinin seçilmesinden ve ardından bu alt kümenin indüklenmiş alt grafiğinin k- çekirdeğinin dikkate alınmasından oluşur . Zayıf birbirine bağlı ağlarda k-çekirdek veya önyükleme süzme işleminde, ara bağlantılar geçişte harici bir alan olarak kabul edilebilir.

algoritmalar

Şöyle Matula ve Beck (1983) tarif sonlu bir grafik olan bir tepe sıralamasını bulmak mümkündür G olarak, sipariş boyama sayısını optimize doğrusal zaman , bir kullanılarak kepçe sıra bulmak ve en küçük derece köşe kaldırmak için tekrar tekrar . Dejenerasyon, kaldırıldığı anda herhangi bir tepe noktasının en yüksek derecesidir. Grafikteki düğüm sayısı n olsun .

Daha ayrıntılı olarak, algoritma aşağıdaki gibi ilerler:

• Bir çıktı listesi başlat L .
• Bir sayı hesaplamak d _v her köşe için v içinde G , komşuları sayısı v halihazırda değildir L . Başlangıçta, bu sayılar sadece köşelerin dereceleridir.
• Bir dizi başlatma D şekilde D [ I ] köşeler bir listesini içerir v halihazırda olmayan L için d _v  =  i .
• k'yi 0'a sıfırlayın .
• n kez tekrarlayın :
  • Dizi hücreler tarama D [0], D , ... bir bulana kadar [1] i olan D [ i ] boş olmayan bir.
  • Set k maks ( k , i )
  • D [ i ]' den bir v tepe noktası seçin . L' nin başına v ekleyin ve D [ i ]' den kaldırın .
  • Her bir komşu için ağırlık ve v değil zaten L , bir tane çıkarma d _ağırlık ve hareket ağırlık yeni değerine karşılık gelen D hücreye d _ağırlık .

Algoritmanın sonunda, k , G'nin dejenerasyonunu içerir ve L , renklendirme numarası için en uygun sırada bir köşe listesi içerir. İ arasında -cores G önek olan L ilave köşe oluşan L sonra k önce daha büyük bir değere alır ya da eşit  i .

L , d _v , D ve k değişkenlerinin başlatılması lineer zamanda kolayca yapılabilir. Her ardışık olarak uzaklaştırıldı köşe bulma v ve hücrelerin ayarlama D komşuları içeren hacim değerine zaman alır orantılı d _v bu adımda; ancak bu değerlerin toplamı, grafiğin kenarlarının sayısıdır (her kenar, iki uç noktasından sonraki toplamdaki terime katkıda bulunur), dolayısıyla toplam zaman doğrusaldır.

Diğer grafik parametreleriyle ilişkisi

Bir G grafiği döngüsel olmayan bir şekilde k derecesiyle yönlendirilirse , o zaman kenarları her düğümün her giden kenarı için bir orman seçilerek k ormana bölünebilir . Bu nedenle, arboricity ait G en da dejenereliğinden eşit olan. Diğer yönde, k tane ormana bölünebilen bir n -köşe grafiği en fazla k ( n  − 1) kenarlıdır ve bu nedenle en fazla 2 k − 1 derecelik bir tepe noktasına sahiptir – bu nedenle dejenerasyon, yozlaşmanın iki katından azdır. ağaçlık. Ayrıca polinom zamanında bir grafiğin, dereceyi en aza indiren, ancak asiklik olması gerekmeyen bir yönelimi hesaplanabilir. Bu tür bir yönlendirme ile bir grafik kenarları içine aynı şekilde bölümlenmiş olabilir k pseudoforests ve bunun tersine bir grafiğin kenarlarının bir bölümü k bir outdegree- için pseudoforests potansiyel k (her pseudoforest için bir outdegree-1 yönlendirme seçerek) yönünde , bu nedenle böyle bir yönelimin minimum derecesi, yine en fazla dejenereliğe eşit olan sözde ağaçlıktır . Kalınlık arboricity sabit bir dahilinde bulunur, ve bu nedenle de dejenere olması.

Bir k -dejenere grafiği, en fazla k  + 1 olan kromatik sayıya sahiptir ; bu, düzlemsel grafikler için altı renk teoreminin kanıtına tam olarak benzeyen, köşe sayısı üzerinde basit bir tümevarımla kanıtlanır. Kromatik sayı, maksimum klik sırasına göre bir üst sınır olduğundan, ikinci değişmez de en fazla dejenerasyon artı birdir. Bir kullanarak hırslı boyama uygun boyama numarası olan bir sipariş üzerine algoritma, bir olabilir renk grafik bir k Dejenere grafiktir en kullanarak k  + 1 renk.

Bir k -vertex-bağlı grafik daha az çıkarılmasıyla birden fazla bileşeni içine bölünemez bir grafiktir k eşdeğer köşe veya köşelerin her biri çift ile bağlanabilir olan bir grafiktir k tepe-ayrık yollar. Bu yollar ayrık kenarlar yoluyla çiftin iki köşesini terk etmek zorunda olduğundan, k -köşe bağlantılı bir grafiğin en az k dejenere olması gerekir . K- çekirdekleri ile ilgili ancak tepe bağlantılarına dayanan kavramlar , sosyal ağ teorisinde yapısal uyum adı altında incelenmiştir .

Bir grafiğin ağaç genişliği veya yol genişliği en fazla k ise , o zaman bu, her bir köşenin en fazla k daha önce komşuya sahip olduğu mükemmel bir eleme sıralamasına sahip olan bir kiriş grafiğinin bir alt grafiğidir . Bu nedenle, dejenerasyon en fazla ağaç genişliğine ve en fazla yol genişliğine eşittir. Ancak, ızgara grafikleri gibi sınırlı dejenere ve sınırsız ağaç genişliğine sahip grafikler vardır .

Burr erdos varsayım bir grafiktir dejeneriliğini ilgilidir G için Ramsey sayısı arasında G , en az N herhangi bir iki-kenar-boyama şekilde N -vertex tam grafik bir tek renkli bir kopyasını içermelidir G . Spesifik olarak, varsayım, herhangi bir sabit k değeri için , k -dejenere grafiklerin Ramsey sayısının, grafiklerin köşelerinin sayısında doğrusal olarak büyüdüğü şeklindedir. Bu varsayım Lee (2017) tarafından kanıtlanmıştır .

sonsuz grafikler

Dejenerasyon ve renk sayısı kavramları sonlu grafikler bağlamında sıklıkla düşünülse de, Erdős & Hajnal'ın (1966) orijinal motivasyonu sonsuz grafikler teorisiydi. Sonsuz bir grafik G için , renklendirme sayısı, sonlu grafikler için yapılan tanıma benzer şekilde, en küçük kardinal sayı α olarak tanımlanabilir, öyle ki , G'nin köşelerinin iyi bir sıralaması vardır, burada her bir köşe noktası α'dan daha az komşuya sahiptir. siparişte daha erken. Renklendirme ve kromatik sayılar arasındaki eşitsizlik bu sonsuz ortamda da geçerlidir; Erdős & Hajnal (1966) , makalelerinin yayınlandığı tarihte zaten iyi bilindiğini belirtmektedir.

Sonsuz kafeslerin rastgele alt kümelerinin dejenerasyonu , önyükleme süzgeci adı altında incelenmiştir .

Ayrıca bakınız

• Grafik teorisi
• ağ bilimi
• Sızma Teorisi
• Çekirdek-çevre yapısı
• Cereceda'nın varsayımı

Notlar

Referanslar