İçeriğe atla

Yönlendirilmiş döngüsüz grafik

Vikipedi, özgür ansiklopedi
Yönlendirilmiş döngüsüz bir grafiğin örneği

Matematikte, özellikle çizge teorisinde ve bilgisayar biliminde, yönlendirilmiş döngüsüz grafik (DAG), yönlendirilmiş döngüsü olmayan bir yönlendirilmiş grafiktir. Yani, köşe ve kenarlardan (ayrıca yaylar olarak da adlandırılır) oluşur ve her kenar bir köşeden diğerine yönlendirilmiştir; böylece bu yönleri takip etmek asla kapalı bir döngü oluşturmaz. Bir yönlendirilmiş grafik, ancak ve ancak köşeleri tüm kenar yönleriyle tutarlı doğrusal bir sıralamayla düzenlemek mümkünse topolojik olarak sıralanabilir ve bu durumda DAG olarak adlandırılır. DAG'ların biyolojiden (örneğin aile ağaçları, epidemiyoloji) bilgi bilimine (örneğin atıf ağları) ve hesaplamaya (örneğin zamanlama) kadar pek çok bilimsel ve hesaplamalı uygulaması vardır.

Yönlendirilmiş döngüsüz grafiklere ayrıca döngüsüz yönlendirilmiş grafikler[1] veya döngüsüz çift grafikler[2] de denir.

Tanımlar

[değiştir | kaynağı değiştir]

Bir graf, köşelerden ve köşe çiftlerini birbirine bağlayan kenarlardan oluşur. Köşeler, kenarlarla çiftler halinde birbirine bağlanmış herhangi bir nesne olabilir. Yönlendirilmiş bir grafta her kenarın bir yönü, bir köşeden diğer köşeye doğru bir yönelimi vardır. Yönlendirilmiş bir grafikteki yol, dizideki her kenarın bitiş köşesinin dizideki bir sonraki kenarın başlangıç köşesiyle aynı olduğu özelliğe sahip bir kenar dizisidir; bir yolun ilk kenarının başlangıç köşesi, son kenarının bitiş köşesine eşitse bir döngü oluşur. Yönlendirilmiş döngüsüz bir grafik, döngüsü olmayan yönlendirilmiş bir grafiktir.[3][4][5]

Yönlendirilmiş bir grafiğin bir köşesi 𝑣, 𝑢 başlayıp 𝑣 biten bir yol varsa başka bir köşe 𝑢 ulaşılabilir olduğu söylenir. Özel bir durum olarak, her köşenin kendisinden (sıfır kenarlı bir yol aracılığıyla) ulaşılabilir olduğu düşünülür. Bir tepe noktası kendisine önemsiz olmayan bir yol (bir veya daha fazla kenarı olan bir yol) aracılığıyla ulaşabiliyorsa, o yol bir döngüdür; dolayısıyla yönlendirilmiş döngüsüz grafikleri tanımlamanın bir başka yolu da, bunların hiçbir tepe noktasının kendisine önemsiz olmayan bir yol aracılığıyla ulaşamadığı grafikler olduğudur.[6]

Matematiksel özellikler

[değiştir | kaynağı değiştir]

Erişilebilirlik ilişkisi, geçişli kapanış ve geçişli indirgeme

[değiştir | kaynağı değiştir]
Bir DAG
Geçişli indirgemesi

Bir DAG'ın erişilebilirlik ilişkisi, DAG'daki köşeler üzerinde tanımlanan bir kısmî sıralama (≤) ile biçimlendirilebilir. Bu kısmî sıralamada, iki köşe u ve v, yalnızca DAG'da u'dan v'ye yönlü bir yol varsa u ≤ v şeklinde sıralanır; yani u, v'ye ulaşabiliyorsa (v, u tarafından erişilebilirse).[7] Ancak farklı DAG'lar aynı erişilebilirlik ilişkisini ve dolayısıyla aynı kısmî sıralamayı verebilir.[8] Örneğin, u → v ve v → w kenarlarına sahip bir DAG ile u → v, v → w ve u → w kenarlarına sahip başka bir DAG, aynı erişilebilirlik ilişkisini oluşturur. Her iki DAG da köşeleri u ≤ v ≤ w şeklinde sıralayan aynı kısmî sıralamayı üretir.

Bir DAG'ın geçişli kapanışı, DAG ile aynı ulaşılabilirlik ilişkisine sahip olan ve en fazla kenara sahip grafiktir. DAG'daki ulaşılabilirlik ilişkisine göre, her bir köşe çifti (u, v) için u → v kenarı bulunur. Bu nedenle, ulaşılabilirlik ilişkisinin ≤, grafik kuramı terimleriyle doğrudan bir çevirisi olarak düşünülebilir.

Aynı yöntemi kısmî sıraları DAG'lara dönüştürmekte daha genel şekilde de kullanmak mümkündür: Her sonlu kısmî sıralı küme (S, ≤) için, S kümesinin her bir elemanı için bir düğüm ve ≤ ilişkisindeki her bir eleman çifti için bir kenar içeren grafik, otomatik olarak geçişli kapanışı olan bir DAG'dır ve (S, ≤) bu DAG’ın ulaşılabilirlik ilişkisini oluşturur. Bu yolla, her sonlu kısmî sıralı küme; bir DAG ile temsil edilebilir.

Üç elemanlı bir kümenin alt kümeleri arasındaki kapsama (⊆) kısmî sırasını gösteren bir Hasse diyagramı

Bir DAG'ın geçişli indirgemesi, DAG ile aynı erişilebilirlik ilişkisine sahip, en az kenara sahip alt grafiktir. DAG’ın erişilebilirlik ilişkisindeki her (u,v) köşe çifti için, u→v kenarı içeren ve DAG'da ayrıca u ile v arasında daha uzun bir yönlü yol bulunan kenarlar çıkartılarak elde edilen bir alt grafiktir. Geçişli kapanışta olduğu gibi, geçişli indirgeme de DAG’lar için benzersiz şekilde tanımlıdır. Buna karşılık, döngü içeren yönlü bir grafikte aynı erişilebilirlik ilişkisini sağlayan birden fazla minimal alt grafik olabilir.[9]

Geçişli indirgemeler, temsil ettikleri kısmî sıralamaların görselleştirilmesinde faydalıdır; çünkü aynı sıralamayı temsil eden diğer grafiklere göre daha az kenara sahiptirler ve bu da daha sade graf çizimlerine olanak tanır. Bir kısmî sıralamanın Hasse diyagramı, her bir kenarın yönünün başlangıç köşesi sona göre daha aşağıda olacak şekilde gösterildiği geçişli indirgeme çizimidir.[10]

Topolojik sıralama

[değiştir | kaynağı değiştir]
DAG topolojik sıralama
Bir DAG'ın topolojik sıralaması: her kenar, sıralamada daha önceki bir noktadan (sol üst) daha sonraki bir noktaya (sağ alt) gider.
DAG geçişli kapanış
Kırmızı kenarlar, mavi DAG üzerine eklenerek geçişli kapanışı oluşturur. Her kenarı için , noktasından erişilebilirdir.
Solda bir yönlendirilmiş döngüsüz grafiğin topolojik sıralaması, sağda ise aynı grafiğin geçişli kapanışı yer almaktadır.

Yönlendirilmiş bir grafiğin topolojik sıralaması, köşelerinin bir dizi halinde öyle bir şekilde sıralanmasıdır ki, her kenar için kenarın başlangıç köşesi, bitiş köşesinden önce gelir. Topolojik bir sıralamaya sahip olan bir graf, döngü içeremez; çünkü bir döngüde en erken sıradaki köşeye gelen kenarın yönü ters olmalıdır. Dolayısıyla, topolojik sıralamaya sahip her grafik döngüsüzdür. Tersine, her yönlendirilmiş döngüsüz grafiğin en az bir topolojik sıralaması vardır.

Topolojik sıralamanın varlığı, yönlendirilmiş döngüsüz grafiklerin eşdeğer bir tanımı olarak da kullanılabilir: Bu grafikler, tam olarak topolojik sıralamaya sahip olan yönlendirilmiş grafiklerdir.[4]

Genel olarak bu sıralama benzersiz değildir; bir DAG (Directed Acyclic Graph – Yönlendirilmiş Döngüsüz Grafik), yalnızca tüm köşeleri içeren yönlendirilmiş bir yola sahipse benzersiz bir topolojik sıralamaya sahiptir. Bu durumda, sıralama köşelerin yolda göründüğü sırayla aynıdır.[11]

Bir DAG'ın topolojik sıralamaları ailesi, DAG için ulaşılabilirlik ilişkisinin doğrusal uzantıları ailesiyle aynıdır.[12] Bu nedenle, aynı kısmi sıralamayı temsil eden herhangi iki grafik, aynı topolojik sıralamalar kümesine sahiptir.

Kombinatoryal sayım

[değiştir | kaynağı değiştir]

Yönlendirilmiş döngüsüz grafiklerin sayılmasıyla ilgili grafik sayım problemi Robinson (1973) tarafından incelenmiştir.[13][14]

n = 0, 1, 2, 3, … için n etiketli köşe üzerindeki DAG sayısı (DAG’ın topolojik sıralamasında bu sayıların hangi sırayla görüneceğine dair kısıtlamalar olmaksızın)

1, 1, 3, 25, 543, 29281, 3781503, … (OEIS'de A003024 dizisi) .

Bu sayılar, özyinelemeli ilişki ile hesaplanabilir.

[13][14]

Eric W. Weisstein tarafından öne sürülen ve McKay et al. (2004) ve arkadaşları tarafından, tüm özdeğerleri pozitif reel sayılar olan (0,1) matrisleri sayısı, yönlendirilmiş döngüsüz grafiklerin (DAG'lerin) sayısıyla aynıdır. Kanıt bire bir eşlemeye (bijektif) dayanır: Bir matris A, yalnızca ve ancak A + I tüm özdeğerleri pozitif olan bir (0,1) matrisiyse bir DAG'in komşuluk matrisidir; burada 'I', birim matrisi belirtir. Bir DAG'in öz döngüsü (self-loop) olamayacağından, komşuluk matrisinin köşegeni sıfırdır; bu nedenle 'I' eklenmesi, tüm matris katsayılarının '0' veya '1' olduğu özelliğini korur.[15]

Çokluağaç (multitree)
Bir çokluağaç: herhangi bir köşeden erişilebilen altgraf, yönsüz bir ağaç oluşturur (örneğin kırmızı olan).
Poliağaç (polytree)
Bir poliağaç: yönsüz bir ağacın kenarlarının yönlendirilmesiyle oluşturulan DAG.

Graf teorisinde ilgili grafik türleri

[değiştir | kaynağı değiştir]

Çoklu ağaç (aynı zamanda kesin olarak belirsiz grafik ya da mangrov olarak da bilinir), herhangi iki köşe arasında en fazla bir yönlendirilmiş yol bulunan bir DAG'dır. Başka bir deyişle, herhangi bir köşeden erişilebilen alt grafik, yönlendirilmemiş bir ağaç oluşturur.[16]

Poliağaç (Polytree), yönlendirilmemiş bir ağacın kenarlarına yön verilerek oluşturulan bir çoklu ağaç türüdür.[17]

Ağaçsal yapı, bir poli ağaç türüdür. Bu yapı, yönlendirilmemiş bir ağacın kenarlarının, kök adı verilen belirli bir düğümden dışa doğru yönlendirilmesiyle oluşur.

Hesaplama problemleri

[değiştir | kaynağı değiştir]

Topolojik sıralama ve tanıma

[değiştir | kaynağı değiştir]

Topolojik sıralama, verilen bir DAG'ın topolojik sıralamasını bulma algoritmik problemidir. Doğrusal zamanda çözülebilir. Kahn'ın topolojik sıralama algoritması, köşe sıralamasını doğrudan oluşturur. Algoritma, topolojik sıralamaya henüz dahil edilmemiş ve diğer köşelerden gelen kenarı olmayan (gelen kenarı bulunmayan) köşelerin bir listesini tutar; başlangıçta bu liste, gelen kenarı olmayan tüm köşeleri içerir. Daha sonra, bu listeden bir köşe seçilerek kısmî topolojik sıralamanın sonuna eklenir ve komşularının bu listeye eklenip eklenmeyeceği kontrol edilir. Bu işlem tüm köşeler işlenene kadar devam eder. Tüm köşeler işlenince algoritma sonlanır.[18] Alternatif olarak, bir topolojik sıralama, bir derinlik öncelikli arama (DFS) grafiği geçişinde postorder numaralandırmasının tersine çevrilmesiyle elde edilebilir.[19]

Belirli bir yönlendirilmiş grafiğin doğrusal zamanda bir DAG olup olmadığını kontrol etmek mümkündür. Bunun için ya bir topolojik sıralama bulunmaya çalışılır ve ardından her kenar için ortaya çıkan sıralamanın geçerli olup olmadığı kontrol edilir,[not 1] ya da alternatif olarak, bazı topolojik sıralama algoritmaları için, algoritmanın hata vermeden tüm köşeleri başarıyla sıralayıp sıralamadığı doğrulanarak bu kontrol yapılabilir.[18]

Döngüsel grafiklerden oluşturma

[değiştir | kaynağı değiştir]

Yönlendirilmemiş herhangi bir grafik, köşeleri için bir toplam sıra seçilerek ve her kenar, sırada önceki uç noktadan sonraki uç noktaya yönlendirilerek bir DAG’a dönüştürülebilir. Ortaya çıkan bu yönelime döngüsüz yönelim denir. Farklı toplam sıralar aynı döngüsüz yönelime yol açabilir. Bu nedenle, n tepe noktasına sahip bir grafik en fazla n! farklı döngüsüz yönelime sahip olabilir. Döngüsüz yönelimlerin sayısı, verilen grafiğin kromatik polinomu olan χ'nin -1 noktasındaki mutlak değeri |χ(−1)| kadar olur.[21]

Sarı yönlü döngüsüz grafik, mavi yönlü grafiğin yoğunlaşmış hâlidir. Mavi grafikteki her bir güçlü bağlantılı bileşen, tek bir sarı tepe noktasına daraltılarak bu yapı oluşturulmuştur.

Herhangi bir yönlendirilmiş grafik, bir geri besleme tepe kümesi veya bir geri besleme yay kümesi (yani tüm döngülere temas eden bir düğüm veya kenar kümesi) kaldırılarak bir DAG’a dönüştürülebilir. Ancak, böyle en küçük kümeyi bulmak NP-zordur (çözümü çok zor ve bilgisayarla kısa sürede hesaplanması mümkün olmayan bir problem türüdür). Keyfi bir yönlendirilmiş grafik, her bir güçlü bağlantılı bileşeni tek bir üst tepe noktasına daraltılarak, yoğunlaşması adı verilen bir DAG’a da dönüştürülebilir.[22] Grafik zaten döngüsüzse, en küçük geri besleme tepe ve yay kümeleri boştur ve yoğunlaşması da grafiğin kendisidir.

Geçiş kapanışı ve geçiş indirgemesi

[değiştir | kaynağı değiştir]

n köşe ve m kenardan oluşan belirli bir DAG'ın geçiş kapanışı, her bir köşeden erişilebilirliği test etmek için sığ öncelikli arama veya derin öncelikli arama kullanılarak O(mn) zamanında oluşturulabilir.[23] Alternatif olarak, ω < 2.373 olmak üzere, bu işlem O(nω) zamanında da çözülebilir. Burada ω, matris çarpım algoritmalarındaki üs değeri olup, bu yöntem yoğun grafikler için O(mn) sınırına kıyasla teorik bir iyileştirme sunar.[24]

Tüm bu geçişli kapanış algoritmalarında, en az iki uzunlukta bir yolla ulaşılabilen köşe çiftlerini, yalnızca bir uzunlukta bir yolla bağlanabilen köşe çiftlerinden ayırt etmek mümkündür. Geçişli indirgeme, uç noktalarını birbirine bağlayan tek yol olan, uzunluğu bir olan yolları oluşturan kenarlardan meydana gelir. Bu nedenle geçişli indirgeme, geçişli kapanışla aynı asimptotik zaman karmaşıklığında oluşturulabilir.[25]

Kapanış problemi

[değiştir | kaynağı değiştir]

Kapanış problemi, girdi olarak tepe ağırlıklı yönlendirilmiş döngüsüz bir grafik alır ve, hiçbir kenarın C'yi terk etmediği bir tepe kümesi

C için, bir kapanışın minimum (veya maksimum) toplam ağırlığını bulmayı hedefler. Bu problem, döngüsüzlük varsayımı olmadan yönlendirilmiş grafikler için de formüle edilebilir, ancak bu durumda daha genel bir biçim elde edilmez; çünkü problem grafiğin yoğunlaştırılması (condensation) üzerindeki aynı problemle özdeştir. Maksimum akış problemine indirgenerek polinomsal zamanda çözülebilir.[26]

Yol algoritmaları

[değiştir | kaynağı değiştir]

Topolojik sıralama ilkesine dayanan bazı algoritmalar, genel grafikler yerine DAG’larda (yönlendirilmiş döngüsüz grafiklerde) kullanıldığında daha basit hale gelir. Örneğin, DAG’larda belirli bir başlangıç köşesinden doğrusal zamanda en kısa ve en uzun yolları bulmak mümkündür. Bu, köşeleri topolojik bir sırayla işleyerek ve her köşe için yol uzunluğunu, gelen kenarlardan herhangi biri üzerinden elde edilen minimum veya maksimum uzunluk olacak şekilde hesaplayarak yapılabilir. Buna karşılık, genel grafiklerde en kısa yolu bulmak, Dijkstra algoritması veya Bellman–Ford algoritması gibi daha yavaş çalışan algoritmalar gerektirebilir. Ayrıca, keyfi grafiklerde en uzun yolu bulmak NP-zor bir problemdir.

Uygulamalar

[değiştir | kaynağı değiştir]

Çizelgeleme

[değiştir | kaynağı değiştir]

Kısmi sıralamaların yönlendirilmiş döngüsüz grafik (DAG) temsilleri, sıralama kısıtlarına sahip görev sistemlerinde çizelgeleme için birçok uygulamaya sahiptir.[27] Bu tür problemlerin önemli bir sınıfı, güncellenmesi gereken nesne kümeleriyle ilgilidir; örneğin, bir hücre değiştirildiğinde bir hesap tablosundaki hücrelerin yeniden hesaplanması ya da kaynak kodu değiştirildiğinde bir bilgisayar yazılımının nesne dosyalarının yeniden oluşturulması gibi durumlar.

Bu bağlamda bir Bağımlılık grafiği, güncellenmesi gereken her nesne için bir köşe ve bir nesnenin diğerinden önce güncellenmesi gerektiğinde bu iki nesne arasında bir kenar içeren bir grafiktir. Bu grafikteki bir döngü Dairesel bağımlılık olarak adlandırılır ve genellikle izin verilmez; çünkü döngüde yer alan görevlerin tutarlı bir şekilde çizelgelenmesi mümkün olmaz. Dairesel bağımlılığı olmayan bağımlılık grafikleri birer DAG oluşturur.[28] Örneğin, bir Elektronik tablo hücresi değiştiğinde, doğrudan ya da dolaylı olarak bu hücreye bağlı olan diğer hücrelerin değerlerinin yeniden hesaplanması gerekir. Bu sorunda çizelgelenmesi gereken görevler, elektronik tablodaki bireysel hücrelerin değerlerinin yeniden hesaplanmalarıdır. Bağımlılıklar, bir hücredeki ifadenin başka bir hücredeki değeri kullanması durumunda ortaya çıkar. Böyle bir durumda, kullanılan değer, bu ifadeden daha önce yeniden hesaplanmalıdır. Bağımlılık grafiğinin topolojik sıralanması ve bu sıralamanın hücre güncellemelerinin çizelgelenmesinde kullanılması, elektronik tablonun her hücre yalnızca bir kez hesaplanarak güncellenmesini sağlar.[29] Benzer görev sıralama sorunları, bir yazılımın derlenmesinde kullanılan Makefile dosyalarında[29] ve düşük seviyeli programların optimize edilmesinde komut çizelgeleme işlemlerinde de ortaya çıkar.[30]

Beş kilometre taşı (10–50 ile etiketlenmiş) ve altı görev (A–F ile etiketlenmiş) içeren bir projenin PERT çizelgesi. İki kritik yol vardır: ADF ve BC.

Planlama kısıtlarının DAG tabanlı biraz farklı bir biçimi, Program değerlendirme ve gözden geçirme tekniği (PERT) tarafından kullanılır. Bu, büyük ölçekli insan projelerinin yönetimi için geliştirilmiş ve DAG'ların ilk uygulamalarından biri olmuştur. Bu yöntemde, bir DAG’ın köşeleri, gerçekleştirilmesi gereken belirli görevleri değil, projenin kilometre taşlarını temsil eder. Bir görev ya da etkinlik ise, ibaşlangıcını ve tamamlanmasını gösteren iki kilometre taşı arasında çizilen bir kenarla temsil edilir. Her bir kenar, bir görev için öngörülen tamamlanma süresiyle etiketlenir. Bu DAG’daki en uzun yol, projenin toplam süresini belirleyen kritik yolu temsil eder. Bireysel kilometre taşları, kendilerine kadar uzanan en uzun yolların uzunluklarına göre zamanlanabilir.[31]

Veri akışı programlama dilleri, veri akışı üzerinde gerçekleştirilen işlemleri ve bazı işlemlerin çıktılarının diğerlerinin girdilerine nasıl bağlandığını tanımlar. Bu diller, aynı döngüsüz bağlı işlem topluluğunun birçok veri öğesine tekrar tekrar uygulandığı durumlarda, tekrarlayan veri işleme görevlerini tanımlamak için oldukça kullanışlıdır. Bu işlemler, her bir işlem için uygun girişler sağlandığı anda paralel bir süreç tarafından yürütülen bir paralel algoritma şeklinde çalıştırılabilir.[32]

Derleyicilerde, düz çizgi kodu (yani, döngü veya koşullu dallanma içermeyen ifade dizileri), kod içinde gerçekleştirilen her bir aritmetik işlemin giriş ve çıkışlarını tanımlayan bir DAG ile temsil edilebilir. Bu temsil, derleyicinin ortak alt ifade giderimi işlemini verimli bir şekilde gerçekleştirmesini sağlar.[33] Daha üst düzeydeki kod organizasyonunda ise, döngüsüz bağımlılıklar ilkesi, büyük bir yazılım sistemindeki modüller veya bileşenler arasındaki bağımlılıkların yönlendirilmiş döngüsüz bir grafik oluşturması gerektiğini belirtir.[34]

Veri işleme ağları

[değiştir | kaynağı değiştir]

Yönlendirilmiş döngüsüz grafik, bir işlem birimleri ağı temsil etmek için kullanılabilir. Bu gösterimde, veri bir işlem birimine gelen kenarlar aracılığıyla girer ve işlem biriminden çıkan kenarlar yoluyla çıkar.

Örneğin, elektronik devre tasarımında, statik kombinasyonel mantık blokları, bir girdinin fonksiyonunu hesaplayan mantık kapısı sistemlerinden oluşan döngüsüz bir yapı olarak temsil edilebilir; burada fonksiyonun girdi ve çıktıları ayrı bitler olarak ifade edilir. Genel olarak, bu blokların çıktısı giriş olarak kullanılamaz; ancak bir kayıtçı veya durum elemanı aracılığıyla yakalanarak döngüsüzlük korunursa kullanılabilir.[35] Kâğıt üzerinde ya da bir veritabanında bulunan elektronik devre şemaları, alt düzey bileşenlere yönlendirilmiş referanslar oluşturan örnekler ya da bileşenler yoluyla yönlendirilmiş döngüsüz grafikler biçimindedir. Ancak, elektronik devrelerin kendileri her zaman yönlendirilmiş ya da döngüsüz olmak zorunda değildir.

İleri beslemeli sinir ağları da başka bir örnektir.

Nedensel yapılar

[değiştir | kaynağı değiştir]
Ana madde: Bayes ağı

Köşeleri belirli bir zamanda gerçekleşen olayları temsil eden ve kenarları daima daha erken bir zamandaki köşeden daha geç bir zamandaki köşeye yönelen çizgeler, zorunlu olarak yönlü ve döngüsüzdür. Bu çizgelerde döngü olmamasının nedeni, çizgede herhangi bir yönlü yol takip edildiğinde köşeye karşılık gelen zamanın her zaman artmasıdır; bu nedenle bir yol boyunca hiçbir zaman bir köşeye geri dönülemez. Bu durum, nedenselliğin yalnızca geleceği etkilediği, geçmişi etkilemediği ve dolayısıyla nedensel döngülerin olmadığı yönündeki doğal sezgimizi yansıtır. Bu tür yönlendirilmiş döngüsüz çizgelere bir örnek, kuantum kütleçekimi için nedensel küme yaklaşımında karşılaşılan çizgelerdir; ancak bu durumda çizgeler geçişli olarak tam kabul edilir. Aşağıdaki sürüm geçmişi örneğinde, yazılımın her bir sürümü genellikle kaydedildiği, işleme alındığı veya yayımlandığı zamana karşılık gelen benzersiz bir zaman ile ilişkilidir. Aşağıdaki atıf çizgesi örneklerinde ise belgeler belirli bir zamanda yayımlanır ve yalnızca kendilerinden önce yayımlanmış belgelere atıfta bulunabilirler.

Bazen olaylar belirli bir fiziksel zamanla ilişkilendirilmez. Ancak olay çiftleri yalnızca nedensel bir ilişkiyle bağlıysa, yani kenarlar olaylar arasındaki nedensel ilişkileri temsil ediyorsa, bu durumda yönlü döngüsüz bir çizge (DAG) oluşur.[36] Örneğin, bir Bayes ağı, olasılıksal olaylar sistemini bir yönlü döngüsüz çizgedeki köşeler olarak temsil eder; bu çizgede bir olayın olasılığı, DAG içindeki kendisinden önce gelen olayların olasılıklarına göre hesaplanabilir.[37] Bu bağlamda, bir DAG'ın ahlaki çizgesi, aynı köşenin ebeveyni olan tüm köşeler arasında (yönsüz) kenarlar eklenerek (buna bazen “evlendirme” denir) ve ardından tüm yönlü kenarların yönsüz hale getirilmesiyle oluşturulan yönsüz bir çizgedir.[38] Benzer nedensel yapıya sahip bir başka çizge türü de etkileşim diyagramlarıdır. Bu diyagramlarda köşeler alınacak kararları veya bilinmeyen bilgileri temsil ederken, kenarlar bir köşeden diğerine olan nedensel etkileri gösterir.[39]Örneğin epidemiyolojide bu tür diyagramlar, müdahale seçenekleri için beklenen değeri tahmin etmek amacıyla sıkça kullanılır.[40][41]

Tersi de doğrudur. Yani, yönlendirilmiş döngüsüz grafikle temsil edilen herhangi bir uygulamada bir nedensel yapı bulunur; bu ya açıkça tanımlanmış bir sıra ya da zamandır (örnekte olduğu gibi) ya da grafik yapısından türetilebilen bir sıralamadır. Bunun nedeni, tüm yönlendirilmiş döngüsüz grafiklerin bir topolojik sıralamasının olmasıdır; yani, düğümlerin öyle bir şekilde sıralanması mümkündür ki tüm kenarlar bu sıralama boyunca aynı yönde ilerler.

Soybilim ve sürüm geçmişi

[değiştir | kaynağı değiştir]
Ptolemaik hanedanının soy ağacı. Hısımlık ilişkileri nedeniyle birçok yakın akraba evliliği soy çizelgesinde çökmeye yol açmıştır.

Soy ağacı grafikleri, her bireyin bir köşe (düğüm) ve her ebeveyn-çocuk ilişkisinin bir kenar olarak gösterildiği yönlendirilmiş çevrimsiz grafikler (DAG) olarak modellenebilir.[42]

Her ne kadar "ağaç" olarak adlandırılsalar da, yakın akrabalar arasında evliliklerin olması (bir çocuğun hem anne hem de baba tarafından ortak ataya sahip olması gibi) nedeniyle bu grafikler mutlaka birer ağaç olmak zorunda değildir ve bu durum soy çizelgesi çökmesine yol açabilir.[43]

Matrilineal (anne-kız) ve patrilineal (baba-oğul) soy çizgileri, bu grafik içinde birer ağaç yapısı oluşturur. Kimse kendi atası olamayacağı için soy ağaçları çevrimsizdir.[44]

Dağıtık sürüm kontrolü sistemlerinin (örneğin Git) sürüm geçmişi genellikle yönlendirilmiş döngüsüz bir grafik (DAG) yapısına sahiptir. Bu yapıda, her bir sürüm için bir tepe noktası bulunur ve doğrudan birbirinden türetilmiş sürüm çiftlerini bağlayan kenarlar yer alır. Bu yapılar, birleştirmeler nedeniyle genellikle bir ağaç değildir.[45]

Rastsal algoritmaların pek çoğunda, özellikle hesaplamalı geometri alanında, algoritma bir geçmiş DAG’ı (history DAG) tutarak, geometrik bir yapının ardışık değişiklikler boyunca sürüm geçmişini temsil eder. Örneğin, Delaunay üçgenleştirmesi için kullanılan rastgele artımlı bir algoritmada, her nokta eklendiğinde mevcut bir üçgen üç küçük üçgenle değiştirilir; ayrıca bazı durumlarda çift üçgen, farklı bir üçgen çifti ile değiştirilerek "devirme" (flip) işlemleri yapılır. Bu algoritmanın geçmiş DAG’ı, oluşturulan her bir üçgen için bir tepe noktası içerir ve her üçgenden, onu değiştiren iki ya da üç üçgene doğru kenarlar vardır. Bu yapı, nokta konumlandırma (point location) sorgularının verimli bir şekilde yanıtlanmasına olanak tanır: sorgu noktası q’nun Delaunay üçgenleştirmesi içinde hangi üçgende yer aldığını bulmak için geçmiş DAG’ta bir yol takip edilir; her adımda, q’yu içeren üçgene geçilir. Bu yolun sonunda ulaşılan üçgen, q’yu içeren Delaunay üçgenidir.[46]

Alıntı grafikleri

[değiştir | kaynağı değiştir]

Bir alıntı grafiği, her biri tek bir yayımlanma tarihine sahip belgelerin tepe noktalarını oluşturduğu bir yönlendirilmiş çevrimsiz grafiktir. Kenarlar, bir belgenin kaynakçasında atıf yaptığı diğer (zorunlu olarak daha erken) belgelere karşılık gelir. Bu tür grafiklerin klasik bir örneği, akademik makaleler arasındaki atıf ilişkileridir. Bu fikir ilk olarak Derek J. de Solla Price tarafından 1965 tarihli "Networks of Scientific Papers" adlı makalede ortaya atılmıştır.[47] Price daha sonra bu tür atıf ağları için ilk matematiksel modeli, Price modelini geliştirmiştir.[48]

Bu bağlamda, bir belgenin atıf sayısı, alıntı grafiğindeki tepe noktasının iç derecesiyle (in-degree) eşdeğerdir. Bu ölçüt, atıf analizi alanında önemli bir yer tutar. Yargı kararları da benzer bir örnektir; hakimler bir davada verdikleri kararı önceki davalara yapılan atıflarla destekleyebilirler. Bir diğer örnek de, patent belgeleridir; yeni bir patent başvurusu, ilgili önceki patentlere (ön sanat olarak da bilinir) atıfta bulunmak zorundadır.

Yönlendirilmiş çevrimsiz grafiklerin özel yapısı, alıntı ağlarının analizinde genel grafik analiz yöntemlerine kıyasla farklı tekniklerin uygulanmasına olanak tanır. Örneğin, transitif indirgeme yöntemi, farklı uygulamalarda gözlenen atıf dağılımları üzerine yeni içgörüler sunar ve farklı bağlamlardaki alıntı oluşturma mekanizmaları arasındaki belirgin farkları ortaya koyar.[49]

Bir diğer teknik olan ana yol analizi (main path analysis), alıntı zincirlerini izleyerek bir alıntı grafiğindeki en önemli atıf yollarını belirlemeye çalışır.

Price modeli, gerçekçi bir atıf ağı modeli olmak için fazla basittir, ancak bazı özellikleri için analitik çözümler elde edilebilecek kadar da basittir. Bu özelliklerin birçoğu, Price modelinin yönsüz bir versiyonu olan Barabási–Albert modelinden türetilen sonuçlar kullanılarak bulunabilir. Bununla birlikte, Price modeli yönlendirilmiş çevrimsiz bir grafik (DAG) ürettiği için, yalnızca yönlendirilmiş çevrimsiz grafiklere özgü özelliklerin analitik olarak hesaplanmasında faydalı bir modeldir. Örneğin, ağa eklenen n'inci düğümden ağdaki ilk düğüme kadar olan en uzun yolun uzunluğu şu şekilde ölçeklenir:[50] .

Veri sıkıştırma

[değiştir | kaynağı değiştir]

Yönlendirilmiş çevrimsiz grafikler, bir dizi dizinin sıkıştırılmış temsili olarak da kullanılabilir. Bu tür bir uygulamada, verilen dizileri oluşturan yolları içeren bir YÇG (DAG) oluşturulur. Pek çok dizinin aynı alt dizileri paylaşması durumunda, bu paylaşılan alt diziler grafik içinde ortak bir bölüm olarak temsil edilebilir ve böylece tüm dizilerin ayrı ayrı listelenmesine kıyasla daha az yer kaplayan bir temsil elde edilir. Örneğin, deterministik çevrimsiz sonlu durum otomatı olarak da bilinen yönlendirilmiş çevrimsiz kelime grafiği (directed acyclic word graph), bilgisayar biliminde kullanılan, tek bir kaynağı olan ve kenarları harfler ya da sembollerle etiketlenmiş bir yönlendirilmiş çevrimsiz grafiktir; bu grafikteki kaynak-sink yolları bir dizi diziyi (örneğin İngilizce kelimeler) temsil eder.[51]

Herhangi bir dizi kümesi, dizilerin her bir ön ekine karşılık gelen düğümler oluşturularak ve bu düğümlerin ebeveynini bir önceki öğeye sahip diziyi temsil edecek şekilde ayarlayarak bir ağaç biçiminde temsil edilebilir; bu şekilde oluşturulan ağaç, trie olarak adlandırılır. Yönlendirilmiş çevrimsiz kelime grafiği, yolların ayrılıp tekrar birleşmesine olanak tanıyarak trie yapısına göre daha az yer kaplar; böylece aynı son ekleri paylaşan kelimeler tek bir ağaç düğümü ile temsil edilebilir.[52]

Aynı yol ailesini temsil etmek için DAG kullanma fikri, ikili karar diyagramında (İKD)[53][54] da görülür; bu yapı, ikili fonksiyonları temsil etmek için DAG tabanlı bir veri yapısıdır.

Bir ikili karar diyagramında, her çöküş (son) düğüm dışındaki düğüm bir ikili değişkenin adıyla etiketlenmiştir ve her kenar ile çöküş düğüm 0 veya 1 ile etiketlenmiştir. Değişkenlere bir doğruluk ataması verildiğinde, fonksiyonun değeri, tekil kaynak düğümden başlayarak, her ara düğümde o düğümdeki değişkenin aldığı değere karşılık gelen kenarı takip ederek ulaşılan çöküş düğümündeki değerdir. Nasıl ki yönlü döngüsüz sözcük grafiklerine trie’lerin sıkıştırılmış bir biçimi olarak bakılabiliyorsa, ikili karar diyagramlarına da, kalan tüm kararlar açısından aynı sonucu veren yolların birleşmesine izin vererek yer tasarrufu sağlayan, karar ağacıların sıkıştırılmış bir biçimi olarak bakılabilir.[55]

Dış bağlantılar

[değiştir | kaynağı değiştir]

Dipnotlar

[değiştir | kaynağı değiştir]
  1. ^ Derinliğe öncelik veren arama tabanlı topolojik sıralama algoritması için, bu geçerlilik kontrolü topolojik sıralama algoritmasının kendisiyle iç içe geçirilebilir.[20]

Kaynakça

[değiştir | kaynağı değiştir]
  1. ^ Thulasiraman, Kandasamy; Swamy, Muthusamy Narasimhan Subramanian (1992). "5.7 Acyclic Directed Graphs". Graphs: Theory and Algorithms. John Wiley and Son. s. 118. ISBN 978-0-471-51356-8. 
  2. ^ Bang-Jensen, Jørgen; Gutin, Gregory Zvi (2008). "2.1 Acyclic Digraphs". Digraphs: Theory, Algorithms and Applications. Springer-Verlag. ss. 32-34. ISBN 978-1-84800-997-4. 
  3. ^ Thulasiraman, Kandasamy; Swamy, Muthusamy Narasimhan Subramanian (1992). "5.7 Acyclic Directed Graphs". Graphs: Theory and Algorithms. John Wiley and Son. s. 118. ISBN 978-0-471-51356-8. 
  4. ^ a b Bang-Jensen, Jørgen; Gutin, Gregory Zvi (2008). "2.1 Acyclic Digraphs". Digraphs: Theory, Algorithms and Applications. Springer-Verlag. ss. 32-34. ISBN 978-1-84800-997-4. 
  5. ^ Christofides, Nicos (1975). Graph Theory: An Algorithmic Approach. Academic Press. ss. 170-174. 
  6. ^ Mitrani, Ilan (1982). Simulation Techniques for Discrete Event Systems. Cambridge Computer Science Texts. 14. Cambridge University Press. s. 27. ISBN 9780521282826. 
  7. ^ Kozen, Dexter (1992). The Design and Analysis of Algorithms. Monographs in Computer Science. Springer. s. 9. ISBN 978-0-387-97687-7. 
  8. ^ Banerjee, Utpal (1993). "Exercise 2(c)". Loop Transformations for Restructuring Compilers: The Foundations. Springer. s. 19. ISBN 978-0-7923-9318-4. 
  9. ^ Bang-Jensen, Jørgen; Gutin, Gregory Zvi (2008). "2.3 Transitive Digraphs, Transitive Closures and Reductions". Digraphs: Theory, Algorithms and Applications. Springer Monographs in Mathematics. Springer. ss. 36-39. ISBN 978-1-84800-998-1. 
  10. ^ Jungnickel, Dieter (2012). Graphs, Networks and Algorithms. Algorithms and Computation in Mathematics. 5. Springer. ss. 92-93. ISBN 978-3-642-32278-5. 
  11. ^ Sedgewick, Robert; Wayne, Kevin (2011). "4.2.25 Unique Topological Ordering". Algorithms. 4. Addison-Wesley. ss. 598-599. ISBN 978-0-13-276256-4. 
  12. ^ Bender, Edward Arthur; Williamson, Stanley Gill (2005). "Örnek 26 (Doğrusal uzantılar – topolojik sıralamalar)". A Short Course in Discrete Mathematics. Dover Books on Computer Science. Courier Dover Publications. s. 142. ISBN 978-0-486-43946-4. 
  13. ^ a b Robinson, Ronald William (1973). "Counting Labeled Acyclic Digraphs". Harary, Frank (Ed.). New Directions in the Theory of Graphs. Academic Press. ss. 239-273. 
  14. ^ a b Harary, Frank; Palmer, Edgar Mowrer (1973). Graphical Enumeration. Academic Press. s. 19. ISBN 978-0-12-324245-7. 
  15. ^ McKay, Brendan Damien; Royle, Gordon Francis; Wanless, Ian Malcolm; Oggier, Frédérique Elise; Sloane, Neil James Alexander; Wilf, Herbert Saul (2004). "Acyclic Digraphs and Eigenvalues of (0,1)-Matrices". Journal of Integer Sequences. Cilt 7. s. 33. arXiv:math/0310423 $2. Article 04.3.3 
  16. ^ Furnas, George William; Zacks, Jeffrey David (1994), "Multitrees: Enriching and Reusing Hierarchical Structure", Proc. SIGCHI Conference on Human Factors in Computing Systems (CHI '94), ss. 330-336, doi:10.1145/191666.191778, ISBN 978-0897916509 
  17. ^ Rebane, George; Pearl, Judea (1987), "The Recovery of Causal Poly-trees from Statistical Data", Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987 (PDF), ss. 222-228 
  18. ^ a b Jungnickel (2012), ss. 50–51.
  19. ^ Cormen, Thomas Haviland; Leiserson, Charles Eric; Rivest, Ronald Linn; Stein, Clifford (2001). Introduction to Algorithms (2 bas.). MIT Press. ss. 549-552. 
  20. ^ Skiena, Steven Sol (2009), The Algorithm Design Manual, Springer, ss. 179-181, ISBN 978-1-84800-070-4 
  21. ^ Stanley, Richard Peter (1973), "Acyclic Orientations of Graphs" (PDF), Discrete Mathematics, 5 (2), ss. 171-178, doi:10.1016/0012-365X(73)90108-8 
  22. ^ Harary, Frank; Norman, Robert Z.; Cartwright, Dorwin (1965), Structural Models: An Introduction to the Theory of Directed Graphs, John Wiley & Sons, s. 63 
  23. ^ Skiena, Steven Sol (2009). The Algorithm Design Manual. Springer. ss. 495. ISBN 978-1-84800-070-4.
  24. ^ Skiena, Steven Sol (2009). The Algorithm Design Manual. Springer. ss. 496. ISBN 978-1-84800-070-4.
  25. ^ Bang-Jensen & Gutin (2008), s. 38.
  26. ^ Picard, Jean-Claude (1976), "Maximal Closure of a Graph and Applications to Combinatorial Problems", Management Science, 22 (11), ss. 1268-1272, doi:10.1287/mnsc.22.11.1268 
  27. ^ Skiena, Steven Sol (2009). The Algorithm Design Manual. Springer. s. 469. ISBN 978-1-84800-070-4.
  28. ^ Al-Mutawa, Hamed Ahmed; Dietrich, Julian; Marsland, Stephen; McCartin, Colin (2014), "On the Shape of Circular Dependencies in Java Programs", 23rd Australian Software Engineering Conference, IEEE, ss. 48-57, doi:10.1109/ASWEC.2014.15, ISBN 978-1-4799-3149-1 
  29. ^ a b Gross, Jonathan Lawrence; Yellen, Jay; Zhang, Ping (2013). "Topological Sorting". Handbook of Graph Theory (2 bas.). CRC Press. s. 1181. ISBN 978-1-4398-8018-0. 
  30. ^ Srikant, Yamini Narayan; Shankar, Priti (2007). The Compiler Design Handbook: Optimizations and Machine Code Generation (2 bas.). CRC Press. ss. 19-39. ISBN 978-1-4200-4383-9. 
  31. ^ Wang, John X. (2002), What Every Engineer Should Know About Decision Making Under Uncertainty, CRC Press, s. 160, ISBN 978-0-8247-4373-4 
  32. ^ Dennis, Jack B. (1974), "First Version of a Data Flow Procedure Language", Programming Symposium, Lecture Notes in Computer Science, 19, ss. 362-376, doi:10.1007/3-540-06859-7_145, ISBN 978-3-540-06859-4 
  33. ^ Touati, Sid; de Dinechin, Benoit (2014), Advanced Backend Optimization, John Wiley & Sons, s. 123, ISBN 978-1-118-64894-0 
  34. ^ Garland, Jeff; Anthony, Richard (2003), Large-Scale Software Architecture: A Practical Guide Using UML, John Wiley & Sons, s. 215, ISBN 9780470856383 
  35. ^ Sapatnekar, Sachin Sharad (2004), Timing, Springer, s. 133, ISBN 978-1-4020-7671-8 
  36. ^ Gopnik, Alison; Schulz, Laura (2007), Causal Learning, Oxford University Press, s. 4, ISBN 978-0-19-803928-0 
  37. ^ Shmulevich, Ilya; Dougherty, Edward R. (2010), Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks, Society for Industrial and Applied Mathematics, s. 58, ISBN 978-0-89871-692-4 .
  38. ^ Cowell, Robert Gethin; Dawid, Alexander Philip; Lauritzen, Steffen Lauritzen; Spiegelhalter, David John (1999), "3.2.1 Moralization", Probabilistic Networks and Expert Systems, Springer, ss. 31-33, ISBN 978-0-387-98767-5 
  39. ^ Dorf, Richard Clayton (1998), The Technology Management Handbook, CRC Press, s. 9–7, ISBN 978-0-8493-8577-3 
  40. ^ Boslaugh, Sarah (2008), Encyclopedia of Epidemiology, Volume 1, SAGE, s. 255, ISBN 978-1-4129-2816-8 
  41. ^ Pearl, Judea (1995), "Causal diagrams for empirical research", Biometrika, 82 (4), ss. 669-709, doi:10.1093/biomet/82.4.669 
  42. ^ Kirkpatrick, Bonnie Berger (Nisan 2011), "Haplotypes versus genotypes on pedigrees", Algorithms for Molecular Biology, 6 (10), s. 10, doi:10.1186/1748-7188-6-10, PMC 3102622 $2, PMID 21504603 
  43. ^ McGuffin, Michael John; Balakrishnan, Ravin (2005), "Genealoji grafiklerinin etkileşimli görselleştirilmesi" (PDF), IEEE Symposium on Information Visualization (INFOVIS 2005), ss. 16-23, doi:10.1109/INFVIS.2005.1532124, ISBN 978-0-7803-9464-3 
  44. ^ Bender, Michael A.; Pemmasani, Giridhar; Skiena, Steven Sol; Sumazin, Pavel (2001), "Yönlendirilmiş çevrimsiz grafiklerde en yakın ortak atayı bulma", On İkinci ACM-SIAM Ayrık Algoritmalar Sempozyumu (SODA '01) Bildirileri, Philadelphia, PA, ABD: Society for Industrial and Applied Mathematics, ss. 845-854, ISBN 978-0-89871-490-6 
  45. ^ Bartlang, Udo (2010), Architecture and Methods for Flexible Content Management in Peer-to-Peer Systems, Springer, s. 59, Bibcode:2010aamf.book.....B, ISBN 978-3-8348-9645-2 
  46. ^ Pach, János; Sharir, Micha (2008). Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures. Mathematical Surveys and Monographs. 152. American Mathematical Society. ss. 93-94. ISBN 978-0-8218-7533-9. 
  47. ^ Price, Derek John de Solla (30 Temmuz 1965), "Networks of Scientific Papers" (PDF), Science, 149 (3683), ss. 510-515, Bibcode:1965Sci...149..510D, doi:10.1126/science.149.3683.510, PMID 14325149 
  48. ^ Price, Derek John de Solla (1976), "A general theory of bibliometric and other cumulative advantage processes", Journal of the American Society for Information Science, 27 (5), ss. 292-306, doi:10.1002/asi.4630270505 
  49. ^ Clough, James Richard; Gollings, Jamie; Loach, Tamar Victoria; Evans, Tim S. (2015), "Transitive reduction of citation networks", Journal of Complex Networks, 3 (2), ss. 189-203, arXiv:1310.8224 $2, doi:10.1093/comnet/cnu039 
  50. ^ Evans, Tim S.; Calmon, Leonardo; Vasiliauskaite, Vykinta (2020), "The Longest Path in the Price Model", Scientific Reports, 10 (1), s. 10503, arXiv:1903.03667 $2, Bibcode:2020NatSR..1010503E, doi:10.1038/s41598-020-67421-8, PMC 7324613 $2, PMID 32601403 
  51. ^ Crochemore, Maxime; Vérin, Renaud (1997), "Direct construction of compact directed acyclic word graphs", Combinatorial Pattern Matching, Lecture Notes in Computer Science, 1264, Springer, ss. 116-129, CiteSeerX 10.1.1.53.6273 $2, doi:10.1007/3-540-63220-4_55, ISBN 978-3-540-63220-7 
  52. ^ M. Lothaire (2005). Applied Combinatorics on Words. Encyclopedia of Mathematics and its Applications. 105. Cambridge University Press. s. 18. ISBN 9780521848022. 
  53. ^ Lee, Chen-Yu (1959). Representation of switching circuits by binary-decision programs. Bell System Technical Journal. 38. ss. 985-999. doi:10.1002/j.1538-7305.1959.tb01585.x. 
  54. ^ Akers, Sheldon B. (1978). Binary Decision Diagrams. IEEE Transactions on Computers. C–27. ss. 509-516. doi:10.1109/TC.1978.1675141. 
  55. ^ Friedman, Stuart James; Supowit, Kenneth John (1987). "Finding the Optimal Variable Ordering for Binary Decision Diagrams". Proc. 24th ACM/IEEE Design Automation Conference (DAC '87). New York, NY, USA: ACM. ss. 348-356. doi:10.1145/37888.37941. ISBN 978-0-8186-0781-3. 
"https://tr.wikipedia.org/w/index.php?title=Yönlendirilmiş_döngüsüz_grafik&oldid=35452597" sayfasından alınmıştır