Erişilebilirlik - Reachability

Olarak grafik teorisi , ulaşılabilirlik bir almak yeteneğini belirtir tepe bir grafik içinde başka. İle başlayan ve ile biten bitişik köşeler dizisi (yani bir yol ) varsa , bir köşe bir köşeye ulaşabilir (ve buradan erişilebilir ) . ${\görüntüleme stili s}$${\görüntüleme stili t}$${\görüntüleme stili t}$${\görüntüleme stili s}$${\görüntüleme stili s}$${\görüntüleme stili t}$

Yönsüz bir grafikte, tüm köşe çiftleri arasındaki erişilebilirlik , grafiğin bağlantılı bileşenleri belirlenerek belirlenebilir . Böyle bir grafikteki herhangi bir köşe çifti, ancak ve ancak aynı bağlantılı bileşene aitlerse birbirine ulaşabilir ; Bu nedenle, bu tür bir grafikte, ulaşılabilirlik simetrik (olup ulaşır IFF ulaşır ). Yönlendirilmemiş bir grafiğin bağlı bileşenleri doğrusal zamanda tanımlanabilir. Bu makalenin geri kalanı, yönlendirilmiş bir grafikte (bu arada, simetrik olması gerekmeyen) ikili erişilebilirliği belirlemenin daha zor sorununa odaklanmaktadır . ${\görüntüleme stili s}$${\görüntüleme stili t}$ ${\görüntüleme stili t}$${\görüntüleme stili s}$

Tanım

Bir yönlendirilmiş grafik için tepe seti ile, ve kenar kümesi , ulaşılabilirlik ilişkisi içinde olan geçişli kapanma ait tüm sipariş çiftleri kümesini demek ki, köşe noktalarının olan köşe bir dizi vardır kenarı bu şekilde olduğu için hepsi . ${\görüntüleme stili G=(V,E)}$${\görüntüleme stili V}$${\görüntüleme stili E}$${\görüntüleme stili G}$${\görüntüleme stili E}$${\görüntüleme stili (s,t)}$${\görüntüleme stili V}$${\displaystyle v_{0}=s,v_{1},v_{2},...,v_{k}=t}$${\displaystyle (v_{i-1},v_{i})}$${\görüntüleme stili E}$${\displaystyle 1\leq i\leq k}$

Eğer bir asiklik , daha sonra kendi erişilebilirlik ilişkisi a, kısmi sıralama ; herhangi bir kısmi düzen bu şekilde, örneğin geçişli indirgemesinin ulaşılabilirlik ilişkisi olarak tanımlanabilir . Bunun bir kayda değer sonucu kısmi siparişler karşıtı simetrik olduğundan eğer, yani ulaşabilir , daha sonra bunu biliyoruz olamaz ulaşmak . Sezgisel olarak, 'den ' e ve ' ye seyahat edebilseydik , o zaman döngüsel olmadığıyla çelişen bir döngü içerirdi. Eğer yöneliktir, ancak değildir (bu en az bir döngüsünü içeren bir deyişle) asiklik, daha sonra kendi erişilebilirlik ilişkisi, bir karşılık gelecek ön sipariş yerine kısmi düzenine. ${\görüntüleme stili G}$${\görüntüleme stili s}$${\görüntüleme stili t}$${\görüntüleme stili t}$ ${\görüntüleme stili s}$${\görüntüleme stili s}$${\görüntüleme stili t}$${\görüntüleme stili s}$${\görüntüleme stili G}$${\görüntüleme stili G}$

algoritmalar

Erişilebilirliği belirleme algoritmaları iki sınıfa ayrılır: ön işleme gerektirenler ve gerektirmeyenler .

Yalnızca bir (veya birkaç) sorgunuz varsa, daha karmaşık veri yapılarının kullanımından vazgeçmek ve istenen çiftin erişilebilirliğini doğrudan hesaplamak daha verimli olabilir. Bu, genişlik ilk arama veya yinelemeli derinleştirme derinlik ilk arama gibi algoritmalar kullanılarak doğrusal zamanda gerçekleştirilebilir .

Çok sayıda sorgu yapacaksanız, daha karmaşık bir yöntem kullanılabilir; kesin yöntem seçimi, analiz edilen grafiğin doğasına bağlıdır. Ön işleme süresi ve fazladan depolama alanı karşılığında, herhangi bir tepe noktasındaki erişilebilirlik sorgularını zaman kadar kısa bir sürede yanıtlayabilen bir veri yapısı oluşturabiliriz . Üç farklı, giderek özelleşen durum için üç farklı algoritma ve veri yapısı aşağıda özetlenmiştir. ${\görüntüleme stili O(1)}$

Floyd-Warshall Algoritması

Floyd-Warshall algoritması yukarıda tanımı olarak erişilebilirlik ilgili sebep olan her türlü yönlendirilmiş grafik, geçişli kapama hesaplamak için kullanılabilir.

Algoritma en kötü durumda zaman ve alan gerektirir . Bu algoritma, tüm köşe çiftleri arasındaki en kısa yol mesafesini hesapladığı için yalnızca erişilebilirlikle ilgilenmez. Negatif döngüler içeren grafikler için en kısa yollar tanımsız olabilir, ancak çiftler arasındaki erişilebilirlik yine de not edilebilir. ${\displaystyle O(|V|^{3})}$${\displaystyle O(|V|^{2})}$

Thorup'un Algoritması

İçin düzlemsel digraphs tarafından tarif edildiği gibi, daha hızlı bir yöntem olup, kullanılabilir Mikkel THORUP içinde ve düz bir grafik üzerinde ulaşılabilirlik sorguları yanıtlayabilir 2004 Bu yöntem geçirdikten sonra zaman içinde bir veri yapısı yaratmak için ön işleme zaman boyutu. Bu algoritma aynı zamanda yaklaşık en kısa yol mesafelerinin yanı sıra rota bilgisi de sağlayabilir. ${\görüntüleme stili O(1)}$${\ Displaystyle O(n\log {n})}$${\ Displaystyle O(n\log {n})}$

Genel yaklaşım, bir tepe noktasından diğer herhangi bir tepe noktasına giden herhangi bir yolun veya ile ilişkili ayırıcılardan en az birinden geçmesi gerektiği şekilde , her bir tepe noktası ile nispeten küçük sözde ayırıcı yollar kümesini ilişkilendirmektir . Erişilebilirlikle ilgili bölümlerin ana hatları aşağıdadır. ${\görüntüleme stili v}$${\görüntüleme stili w}$${\görüntüleme stili v}$${\görüntüleme stili w}$

Bir grafik verildiğinde , algoritma, köşeleri rastgele bir tepe noktasından başlayarak katmanlar halinde düzenleyerek başlar . Katmanlar her şeyden önce köşeler ulaşılamadı.Ancak dikkate alınarak alternatif adımda inşa edilir gelen önceki aşamada (hemen başlayarak ) ve daha sonra erişim bütün çıkıntılar için tüm noktaların bir katmana atanmış kadar önceki aşamada. Katmanların oluşturulmasıyla, her köşe en fazla iki katman görünür ve içindeki her yönlendirilmiş yol veya iki yol , iki bitişik katman ve içinde bulunur . Izin olduğunu Oluşturulan son katman, için en düşük değere olmak öyle ki . ${\görüntüleme stili G}$${\displaystyle v_{0}}$${\displaystyle v_{0}}$${\görüntüleme stili G}$${\görüntüleme stili L_{i}}$${\displaystyle L_{i+1}}$${\görüntüleme stili k}$${\görüntüleme stili k}$${\displaystyle \bigcup _{i=0}^{k}L_{i}=V}$

Grafik sonra digraphs bir dizi olarak ifade re her ve tüm önceki düzeyde daralma olan tek bir tepe olarak. Her dipat en fazla iki ardışık katmanda göründüğünden ve her biri iki ardışık katmandan oluşturulduğundan, içindeki her dipat kendi bütünlüğü içinde en az birinde (ve bu tür ardışık 2'den fazla olmayan grafikte) görünür.${\displaystyle G_{0},G_{1},\ldots ,G_{k-1}}$${\displaystyle G_{i}=r_{i}\cup L_{i}\cup L_{i+1}}$${\görüntüleme stili r_{i}}$${\displaystyle L_{0}\ldots L_{i-1}}$${\görüntüleme stili G_{i}}$${\görüntüleme stili G}$${\görüntüleme stili G_{i}}$

Her biri için , kaldırıldığında grafiği, her biri orijinalin en fazla köşelerini içeren üç bileşene bölen üç ayırıcı tanımlanır . De karşılıklı dipaths iki kat inşa edilmiştir, her bir ayırıcı ayırıcılar tüm 6 dipaths için kadar bir toplam, 2 dipaths için kadar meydana gelebilir. Let dipaths bu seti olsun. Bu tür ayırıcıların her zaman bulunabileceğinin kanıtı Lipton ve Tarjan'ın Düzlemsel Ayırıcı Teoremi ile ilgilidir ve bu ayırıcılar lineer zamanda bulunabilir. ${\görüntüleme stili G_{i}}$${\ Displaystyle 1/2}$${\görüntüleme stili G_{i}}$${\görüntüleme stili S}$

Her biri için yönlendirilmiş doğası , yolun başlangıcından sonuna kadar köşelerinin doğal bir indekslenmesini sağlar. 'deki her köşe için , ile ulaşılabilen ilk köşeyi ve 'ye ulaşan son köşeyi buluruz . Olduğunu, nasıl erken içine bakıyoruz biz alabileceğiniz ve ne kadar biz kalabilirler ve hala geri almak . Bu bilgiler her biri ile birlikte saklanır . Sonra herhangi bir köşe çifti için ve , ulaşabilir aracılığı eğer üzere bağladığı daha erken gelen bağlarla . ${\ Displaystyle Q\ S}$${\görüntüleme stili Q}$${\görüntüleme stili v}$${\görüntüleme stili G_{i}}$${\görüntüleme stili Q}$${\görüntüleme stili v}$${\görüntüleme stili Q}$${\görüntüleme stili v}$${\görüntüleme stili Q}$${\görüntüleme stili v}$${\görüntüleme stili Q}$${\görüntüleme stili v}$${\görüntüleme stili v}$${\görüntüleme stili u}$${\görüntüleme stili w}$${\görüntüleme stili u}$${\görüntüleme stili w}$ ${\görüntüleme stili Q}$${\görüntüleme stili u}$${\görüntüleme stili Q}$${\görüntüleme stili w}$${\görüntüleme stili Q}$

Oluşturan özyinelemenin her adımı için her köşe yukarıdaki gibi etiketlenir . Bu özyineleme logaritmik derinliğe sahip olduğundan, köşe başına toplam ek bilgi depolanır. Bu noktadan itibaren, erişilebilirlik için logaritmik bir zaman sorgusu, ortak, uygun bir . Orijinal kağıt daha sonra sorgu süresini . ${\displaystyle G_{0}\ldots ,G_{k}}$${\ Displaystyle O(\log {n})}$${\görüntüleme stili Q}$${\görüntüleme stili O(1)}$

Bu yöntemin analizini özetlerken, ilk olarak, katmanlama yaklaşımının her bir köşe noktasının yalnızca kez dikkate alınması için köşeleri bölümlere ayırdığını düşünün . Algoritmanın ayırıcı aşaması, grafiği, en fazla orijinal grafiğin boyutunda olan bileşenlere bölerek , logaritmik bir özyineleme derinliği ile sonuçlanır. Özyinelemenin her düzeyinde, ayırıcıları ve köşeler arasındaki olası bağlantıları tanımlamak için yalnızca doğrusal çalışmaya ihtiyaç vardır. Genel sonuç, yalnızca her köşe için depolanan ek bilgilerle ön işleme süresidir . ${\görüntüleme stili O(1)}$${\ Displaystyle 1/2}$${\ Displaystyle O(n\log n)}$${\ Displaystyle O(\log {n})}$

Kameda'nın Algoritması

Kameda'nın yöntemine uygun bir digraf eklenmiş ve eklenmiştir.${\görüntüleme stili s}$${\görüntüleme stili t}$

Her köşe için DFS etiketlerini gösteren, Kameda'nın algoritması çalıştıktan sonra yukarıdakiyle aynı grafik

1975'te T. Kameda'dan dolayı ön işleme için daha da hızlı bir yöntem, eğer grafik düzlemsel , asiklik ise kullanılabilir ve ayrıca aşağıdaki ek özellikleri sergiler: tüm 0 dereceli ve tüm 0 dereceli köşeler aynı üzerinde görünür yüz (genellikle dış yüzü olduğu varsayılır) ve tüm 0-alıcılık köşe, bir kısmında görünür böyle iki bölüme o yüzün sınırını bölümlemek mümkündür ve tüm 0-outdegree köşe diğer görünür (yani iki tür köşe birbirini değiştirmez).

Eğer sergiler bu özellikler, o zaman sadece grafiği ön işlemeden olabilir zaman ve sadece depolamak köşe noktalarının herhangi çifti için ulaşılabilirlik sorguları yanıtlayan vertex ekstra bit basit karşılaştırma ile zaman. ${\görüntüleme stili G}$${\görüntüleme stili O(n)}$${\ Displaystyle O(\log {n})}$${\görüntüleme stili O(1)}$

Ön işleme aşağıdaki adımları gerçekleştirir. Her 0 derecelik tepe noktasına bir kenarı olan yeni bir tepe noktası ve her 0 derecelik tepe noktasından kenarları olan başka bir yeni tepe noktası ekleriz. Özelliklerinin düzlemselliği korurken bunu yapmamıza izin verdiğini, yani bu eklemelerden sonra hala kenar geçişlerinin olmayacağını unutmayın. Her köşe için, grafiğin düzlemselliğine göre (örneğin, grafiğin gömülmesine göre saat yönünde) bitişikliklerin (dış kenarlar) listesini saklarız. Daha sonra bir sayacı başlatır ve 'den bir Derinlik-İlk Geçişi başlatırız . Bu geçiş sırasında, her bir köşenin komşuluk listesi, gerektiğinde soldan sağa ziyaret edilir. Çapraz geçiş yığınından köşeler çıkarıldığında, değer ile etiketlenir ve ardından azaltılır. Not hep değerle etiketlenir ve her zaman etiketlenen . Önce derinlik geçişi daha sonra tekrarlanır, ancak bu sefer her bir köşenin bitişik listesi sağdan sola ziyaret edilir. ${\görüntüleme stili s}$${\görüntüleme stili t}$${\görüntüleme stili G}$${\ Displaystyle i=n+1}$${\görüntüleme stili s}$${\görüntüleme stili ben}$${\görüntüleme stili ben}$${\görüntüleme stili t}$${\ Displaystyle n+1}$${\görüntüleme stili s}$${\görüntüleme stili 0}$

Tamamlandığında ve ve bunların olay kenarları kaldırılır. Her Kalan tepe değerleri içeren bir 2 boyutlu etiket depolar için . İki kesişim noktası Verilen ve ve bunların etiketler ve biz söylemek ancak ve ancak , ve en az bir bileşeni vardır ya az kesinlikle hangi veya sırasıyla. ${\görüntüleme stili s}$${\görüntüleme stili t}$${\görüntüleme stili 1}$${\görüntüleme stili n}$${\görüntüleme stili u}$${\görüntüleme stili v}$${\displaystyle L(u)=(a_{1},a_{2})}$${\displaystyle L(v)=(b_{1},b_{2})}$${\görüntüleme stili L(u)<L(v)}$${\displaystyle a_{1}\leq b_{1}}$${\displaystyle a_{2}\leq b_{2}}$${\displaystyle a_{1}}$${\ Displaystyle a_{2}}$${\displaystyle b_{1}}$${\ Displaystyle b_{2}}$

Bu yöntemin ana sonucu, daha sonra , zaman içinde kolayca hesaplanan if ve yalnızca if öğesinden ulaşılabilir olduğunu belirtir . ${\görüntüleme stili v}$${\görüntüleme stili u}$${\görüntüleme stili L(u)<L(v)}$${\görüntüleme stili O(1)}$

İlgili sorunlar

İlgili bir sorun, bir dizi köşe hatasıyla erişilebilirlik sorgularını çözmektir . Örneğin: " Köşeler başarısız olmasına ve artık kullanılamamasına rağmen tepe noktası yine de tepe noktasına ulaşabilir mi?" Benzer bir problem, tepe noktası arızalarından ziyade uç arızalarını veya ikisinin bir karışımını dikkate alabilir. Genişlik öncelikli arama tekniği, bu tür sorgularda da işe yarar, ancak verimli bir kehanet oluşturmak daha zordur. ${\görüntüleme stili k}$${\görüntüleme stili u}$${\görüntüleme stili v}$${\displaystyle s_{1},s_{2},...,s_{k}}$

Erişilebilirlik sorgularıyla ilgili diğer bir sorun, grafiğin bir kısmı değiştirildiğinde erişilebilirlik ilişkilerindeki değişiklikleri hızla yeniden hesaplamaktır. Örneğin, bu, belleğin geri kazanılmasını (böylece yeniden tahsis edilebilmesi için) çalışan uygulamanın performans endişeleriyle dengelemesi gereken çöp toplamayla ilgili bir endişedir .

Ayrıca bakınız

• Gamoid
• st -bağlanabilirlik

Referanslar