Bağlantılı Bileşenler – Bilgisayar Bilimleri Ödevleri – Bilgisayar Bilimleri Ödev Hazırlatma – Bilgisayar Bilimleri Alanında Tez Yazdırma – Bilgisayar Bilimleri Ödev Yaptırma Fiyatları
Güçlü Bağlantılı Bileşenler
Şimdi güçlü bileşenlerin, yani yönlendirilmiş grafiklerde güçlü bir şekilde bağlantılı maksimum alt çizgelerin hesaplanmasını ele alıyoruz. Yönsüz grafiklerdeki iki bağlantılı bileşenlerin hesaplanmasına benzer şekilde, köşeleri 1’den n’ye kadar ardışık sayılarla etiketleyen değiştirilmiş bir derinlik öncelikli arama kullanırız. Geçişin tüm köşeleri keşfetmeden sona ermesi durumunda, DFS’yi şimdiye kadar etiketlenmemiş bir tepe noktasında yeniden başlatmamız gerekir. Sonuç, yayılan bir F ormanıdır.
DFS geçişi sırasında denetlenen e = (v, w) kenarları aşağıdaki kategorilere ayrılır:
1. Etiketlenmemiş köşelere götüren tüm kenarlara ağaç kenarları denir (bunlar DFS ormanının ağaçlarına aittir).
2. Daha önceki bir adımda zaten etiketlenmiş olan w köşesine işaret eden kenarlar aşağıdaki sınıflara girer:
a) Eğer num[w] > num[v] ise e’ye ileri kenar deriz.
b) Aksi takdirde, eğer w aynı DFS ağacında v’nin atası ise e a deriz.
c) Aksi takdirde e’ye çapraz kenar denir (çünkü bir alt ağaçtan diğerine işaret eder).
İki v, w köşesi, ancak ve ancak v’den w’ye ve w’den v’ye yönlendirilmiş yollar varsa aynı güçlü bileşendedir. Köşeler birden fazla bileşene ait olabilirken kenar kümesi bölümlenmiştir. DFS geçişi sırasında, güçlü bileşenlerin köklerini, yani her bileşende en küçük DFS etiketli tepe noktasını tespit etmek istiyoruz.
İki bağlantılı bileşenler durumunda olduğu gibi, bir v köşesinin her bir w alt öğesi için w’den v’ye geri götüren yönlendirilmiş bir yol olup olmadığına karar vermeliyiz. Şimdi herhangi bir köşenin en küçük etiketi olarak tanımlıyoruz. en fazla bir arka veya çapraz kenar tarafından takip edilen keyfi olarak birçok ağaç yayı aracılığıyla ulaşılabilen aynı güçlü bileşen söz konusudur.
Bir köşe v, ancak ve ancak aşağıdaki koşulların her ikisi de karşılandığında güçlü bir bileşenin köküdür:
1. v’den veya onun soyundan birinden v’nin bir atasına kadar geriye doğru bir kenar yoktur.
2. v’nin güçlü bileşeninin kökü v’nin atası olacak şekilde v’den veya onun soyundan gelenlerden birinden w tepe noktasına çapraz kenar (v, w) yoktur. Bu, lowlink[v] = num[v] olup olmadığı kararıyla eşdeğerdir.
Tersine, koşulun geçerli olduğunu ancak u’nun, v’nin u̸= v ile güçlü bileşeninin kökü olduğunu varsayalım. v’den u’ya yönlendirilmiş bir yol olmalıdır. Bu yolun, DFS ağacında v’nin alt öğesi olmayan bir w tepe noktasına işaret eden ilk kenarı, bir arka veya çapraz kenardır. Bu, lowlink[v] ≤ num[w] < num[v] anlamına gelir, çünkü v ve w’nin en yüksek numaralı ortak atası da bu güçlü bileşendedir.
← Eğer v, gerçek kapsayan ormandaki güçlü bir bileşenin kökü ise, lowlink[v] = num[v] olduğu sonucuna varabiliriz. Tersini varsayarsak (yani, lowlink[v] < num[v]), v’nin bazı uygun ataları aynı güçlü bileşene ait olacaktır. Böylece v, SCC’nin kökü olmaz.
Bu ispatı sonuçlandırır. DFS geçişi sırasında keşfedilen tüm köşeleri bir yığına koyarsak (iki bağlantılı bileşenlerin hesaplanmasındaki kenar yığınına benzer şekilde), lemma, grafiğin güçlü bir şekilde bağlı bileşenlerini ‘kesmemize’ izin verir.
Yukarıdaki algoritmaların, grafikteki döngülerin saptanmasına dayalı olmalarından dolayı benzerliklerini paylaştığı açıktır. Basit döngüler (iki bağlantılı bileşenler için) yerine rastgele düşünülürse, bu yaklaşım köprü (veya 2-kenar) bağlantılı bileşenleri hesaplayan benzer bir üçüncü algoritma verir.
Grafik ile ilgili ilk sonuçlar sağlandı. Altmışlarda, bir grafiği üç bağlantılı bileşenlerine bölmek için derinlik öncelikli aramaya dayalı doğrusal bir zaman algoritması yayınladılar.
Verimli bir paralel uygulama ile birlikte açık kulak ayrıştırmalarını bulmaya yönelik bir yönteme dayalı başka bir algoritma sağladı. İlk Hopcroft/Tarjan algoritmasının yanlış olduğu ortaya çıktı ve daha sonra bu algoritma değiştirildi. SPQR ağaçlarının doğru doğrusal zaman uygulamasını elde etmek için hatalı parçaları değiştirdiler. Şimdi algoritmalarını kısaca gözden geçirelim.
Bağlantılı küme örnekleri
Topoloji Ayırma Aksiyomları
Topoloji Ders Notları
Topoloji kompaktlık
Topoloji Kitabı PDF
Topoloji ders anlatımı
Topoloji çözümlü Sorular PDF
Topolojik Uzaylarda SÜREKLİLİK
(a, b) çifti, G’nin kenarlarını denklik sınıfları E1, . . . , Ek (ayırma sınıfları), s.t. iki kenar, iç tepe noktası olarak ne a ne de b içermeyen bir p yolu üzerinde bulunuyorsa, yani a veya b içeriyorsa, p’nin uç tepe noktasıysa, tam olarak aynı sınıfa aittir.
(a,b) çifti, aşağıdaki özel durumlar dışında en az iki ayırma sınıfı varsa bir ayırma çiftidir: tam olarak iki ayırma sınıfı vardır ve bunlardan biri tek kenardan oluşur veya tam olarak üç tane varsa Hepsi tek bir kenardan oluşan ayırma sınıfları. Hiçbir ayırma çifti içermiyorsa, G grafiği üç bağlantılıdır.
E1..k sınıflarında E′ = li=1 Ei olmak üzere iki gruba ayrılacak ve E” = ki=l+1 Ei, s.t. her grup en az iki kenar içerir. G’ = (V(E’ ∪e),E’ ∪e) ve G” = (V(E” ∪e),E” ∪e) adlı iki grafik bölüm [E’, E”] ve her bir parçaya yeni sanal kenar e = (a, b) eklenmesi, G’nin bölünmüş grafikleri olarak adlandırılır (ve bunlar yine iki bağlantılıdır).
Bölme işlemi, bölünmüş grafiklere yinelemeli olarak uygulanırsa, bu, G’nin (mutlaka benzersiz olması gerekmez) bölünmüş bileşenlerini verir. E’deki her kenar, tam olarak bir tane içinde ve her sanal kenar, tam olarak iki bölünmüş bileşende bulunur.
G’nin kenar sayısı üzerindeki tümevarım: Eğer |E| = 3, G bölünemez ve lemma doğrudur. Şimdi, lemmanın en fazla m – 1 kenarı olan grafikler için doğru olduğunu varsayalım.
Grafiğin m kenarı varsa, G bölünemezse lemma açıkça doğrudur. Aksi takdirde G, k + 1 ve m – k + 1 kenarları 2 ≤ k ≤ m – 2 olan iki grafiğe bölünebilir. Varsayımla, toplam kenar sayısı 3(k+1)−6+3 ile sınırlıdır. (m−k+1)−6 = 3m−6. Böylece, kenar sayısı üzerinde tümevarımla ispat tamamlanmış olur.
Üç türden bölünmüş bileşenler vardır: üçlü bağlar (iki köşe arasındaki üç kenar), üçgenler (3 uzunluğundaki döngüler) ve üç bağlantılı basit grafikler. Şimdi bölme işleminin tersini tanıtıyoruz: her ikisi de aynı sanal kenarı e içeren G1 = (V1,E1) ve G2 = (V2,E2) iki grafiğin birleştirme grafiğidir.
Bir grafiğin üç bağlı bileşenleri, bölünmüş bileşenlerinden, üçlü bağların mümkün olduğu kadar çoklu bağlara birleştirilmesiyle ve üçgenlerin mümkün olduğunca çokgenler oluşturmak için birleştirilmesiyle elde edilir. (Muhtemelen benzersiz olmayan) bölme ve birleştirmeden bağımsız olarak, aynı üç bağlantılı bileşenleri elde ettiğimizi gösterdi.
Bağlantılı küme örnekleri Topoloji Ayırma Aksiyomları Topoloji çözümlü Sorular PDF Topoloji ders anlatımı Topoloji ders NOTLARI Topoloji Kitabı PDF Topoloji kompaktlık Topolojik Uzaylarda SÜREKLİLİK