Bileşen (grafik teorisi) - Component (graph theory)

Üç bileşenli bir grafik.

Olarak grafik teorisi , bir bileşen, bir ait yönsüz grafik bir olduğunu kaynaklı alt grafiğinin herhangi iki ettiği noktalar vardır bağlı birbirlerine yolları ve hangi grafiğin geri kalanı ilave köşe bağlanır. Örneğin, çizimde gösterilen grafiğin üç bileşeni vardır. Olay kenarları olmayan bir tepe noktasının kendisi bir bileşendir. Kendisi bağlantılı bir grafiğin, grafiğin tamamından oluşan tam olarak bir bileşeni vardır. Bileşenlere bazen bağlı bileşenler de denir .

denklik bağıntısı

Bileşenleri tanımlamanın alternatif bir yolu , grafiğin köşelerinde tanımlanan bir denklik ilişkisinin denklik sınıflarını içerir . Bir yönsüz grafikte, bir köşe V olan ulaşılabilir bir tepe noktasından u bir yol olup olmadığını u için v . Bu tanımda, tek bir tepe noktası, uzunluğu sıfır olan bir yol olarak sayılır ve aynı tepe, bir yol içinde birden fazla kez meydana gelebilir. Ulaşılabilirlik bir denklik bağıntısıdır , çünkü:

Öyle dönüşlü : kendisine herhangi tepe noktasından uzunluğu sıfır önemsiz bir yol yoktur.
Bu ise , simetrik : bir yol varsa u için v , aynı kenarlar bir yol oluşturmak v için u .
Bu ise geçişli : bir yol varsa u için v ve bir yol v için ağırlık , iki yol bir yol oluşturmak için bir araya birleştirilmiş olabilir u için ağırlık .

Bileşenler daha sonra bu ilişkinin denklik sınıfları tarafından oluşturulan indüklenmiş alt grafiklerdir .

Bileşen sayısı

Bileşenlerin sayısı, bir grafiğin önemli bir topolojik değişmezidir . Gelen topolojik grafik teorisi bu sıfırıncı olarak yorumlanabilir Betti sayıda grafik. Gelen cebirsel grafik teorisi bir şekilde 0 sayıda eşit özdeğerinin ait Laplace matris grafiğinin. Aynı zamanda bir grafiğin kromatik polinomunun sıfır olmayan ilk katsayısının indeksidir . Bileşenlerin sayısı Tutte teoreminde , mükemmel eşleşmelere sahip grafikleri karakterize etmede ve grafik tokluğunun tanımında önemli bir rol oynar .

algoritmalar

Genişlik öncelikli arama veya derinlik öncelikli arama kullanılarak bir grafiğin bileşenlerini doğrusal zamanda (grafiğin köşe ve kenar sayıları açısından) hesaplamak kolaydır . Her iki durumda da, belirli bir v noktasında başlayan bir arama, dönmeden önce v'yi içeren (ve daha fazlasını içermeyen) tüm bileşeni bulacaktır . Bir grafiğin tüm bileşenlerini bulmak için, köşeleri arasında döngü yapın, döngü önceden bulunan bir bileşene dahil edilmemiş bir tepe noktasına ulaştığında önce yeni bir genişlik veya ilk önce derinlik araması başlatın. Hopcroft & Tarjan (1973) esasen bu algoritmayı tanımlar ve o noktada "iyi bilindiğini" belirtir.

Ayrık kümeli veri yapılarının basit bir uygulaması olarak köşeler ve kenarlar eklendikçe grafiğin bileşenlerini dinamik olarak izlemek için etkili algoritmalar da vardır . Bu algoritmalar, işlem başına itfa edilmiş O( α ( n )) zaman gerektirir ; burada köşeleri ve kenarları eklemenin ve bir köşenin düştüğü bileşenin belirlenmesinin her ikisi de işlemdir ve α ( n ) çok hızlı büyüyen çok yavaş büyüyen bir tersidir. Ackermann işlevi . İlgili bir sorun, tüm kenarlar bir grafikten birer birer silindiği için bileşenlerin izlenmesidir; bunu sorgu başına sabit zamanla ve veri yapısını korumak için $O(| V || E |)$ zamanla çözmek için bir algoritma mevcuttur ; bu, kenar silme başına itfa edilmiş $O(| V |)$ maliyetidir . İçin orman , maliyet azaltılabilir $(O q | + V | günlük | V |)$ ya da $O (giriş | V |)$ sıyırma yöntemi (başına maliyet itfa Shiloach ve bile 1981 ).

Araştırmacılar ayrıca, çalışan belleğin logaritmik bir bit sayısıyla ( L karmaşıklık sınıfı tarafından tanımlanır) sınırlı olduğu programlar gibi daha sınırlı hesaplama modellerinde bileşenleri bulmak için algoritmalar üzerinde çalıştılar . Lewis ve Papadimitriou (1982) , iki köşenin yönsüz bir grafiğin aynı bileşenine ait olup olmadığını loguzayda test etmenin mümkün olup olmadığını sormuş ve logspace-bağlantıya eşdeğer problemlerin bir karmaşıklık sınıfı SL tanımlamıştır . Sonunda Reingold (2008) , bu bağlantı problemini logaritmik uzayda çözmek için L = SL olduğunu gösteren bir algoritma bulmayı başardı .

Rastgele grafiklerdeki bileşenler

Rastgele grafiklerde bileşenlerin boyutları, sırayla belirli modele bağlı olan bir rastgele değişken tarafından verilir.

Model görünüşte farklı davranışı ile üç bölge var: ${\görüntüleme stili G(n,p)}$

kritik altı ${\görüntüleme stili np<1}$: Tüm bileşenler basit ve çok küçüktür, en büyük bileşenin boyutu vardır ; $|C_{1}|=O(\log n)$

kritik ${\ Displaystyle np=1}$: $|C_{1}|=O(n^{2/3})$ ;

süper kritik $np>1$: $|C_{1}|\yaklaşık yn$ denklemin pozitif çözümü nerede ${\görüntüleme stili y=y(np)}$ $e^{-pny}=1-y.$

burada ve sırasıyla en büyük ve ikinci en büyük bileşenlerdir. Diğer tüm bileşenlerin sipariş boyutları vardır ${\görüntüleme stili C_{1}}$ ${\ Displaystyle C_{2}}$ ${\görüntüleme stili O(\log n).}$

Ayrıca bakınız

dev bileşen
Güçlü bağlantılı bileşen , yönlendirilmiş grafikler için ilgili bir kavram
İki bağlantılı bileşen
Yönlendirilmemiş grafiklerde bileşenlerin uygun bir şekilde genelleştirilmesi için modüler ayrıştırma
Bağlantılı bileşen etiketleme , grafik bileşenlerine dayalı bilgisayar görüntü analizinde temel bir teknik
Sızma teorisi , ızgara grafiklerinin rastgele alt grafiklerinde bileşenlerin davranışını açıklayan bir teori
merkezilik
Köprü (grafik teorisi)

Referanslar

Hopcroft, J .; Tarjan, R. (1973), "Algoritma 447: grafik işleme için verimli algoritmalar", Communications of the ACM , 16 (6): 372–378, doi : 10.1145/362248.362272
Lewis, Harry R. ; Papadimitriou, Christos H. (1982), "Simetrik uzay-sınırlı hesaplama", Teorik Bilgisayar Bilimi , 19 (2): 161–187, doi : 10.1016/0304-3975(82)90058-5
Reingold, Omer (2008), "Log-space'de yönsüz bağlantı", Journal of the ACM , 55 (4): Madde 17, 24 sayfa, doi : 10.1145/1391289.1391291
Shiloach, Yossi; Even, Shimon (1981), "On-line kenar silme problemi", Journal of the ACM , 28 (1): 1–4, doi : 10.1145/322234.322235

Dış bağlantılar

Yönsüz grafiklerde bileşenleri bulmak için MATLAB kodu , MATLAB Dosya Değişimi.
Bağlı bileşenler , Steven Skiena, The Stony Brook Algorithm Repository

Languages

In other projects