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

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 veya döngüsüz çift grafikler de denir.

 Tanımlar 
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.

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.

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

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). Ancak farklı DAG'lar aynı erişilebilirlik ilişkisini ve dolayısıyla aynı kısmî sıralamayı verebilir. Ö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.
küçükresim|300x300pik| Üç 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.

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.

 Topolojik sıralama 

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.

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.

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

 Kombinatoryal sayım 
Yönlendirilmiş döngüsüz grafiklerin sayılmasıyla ilgili grafik sayım problemi  tarafından incelenmiştir.

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, …  .

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



Eric W. Weisstein tarafından öne sürülen ve  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.

 Graf teorisinde ilgili grafik türleri 
Ç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.

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

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 
 Topolojik sıralama ve tanıma 
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., ss. 50–51. 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.

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, 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.

 Döngüsel grafiklerden oluşturma 
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,  tepe noktasına sahip bir grafik en fazla  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  kadar olur.
küçükresim|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. 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 
 köşe ve  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  zamanında oluşturulabilir.Skiena, Steven Sol (2009). The Algorithm Design Manual. Springer. ss. 495. ISBN 978-1-84800-070-4. Alternatif olarak,  olmak üzere, bu işlem  zamanında da çözülebilir. Burada ω, matris çarpım algoritmalarındaki üs değeri olup, bu yöntem yoğun grafikler için  sınırına kıyasla teorik bir iyileştirme sunar.Skiena, Steven Sol (2009). The Algorithm Design Manual. Springer. ss. 496. ISBN 978-1-84800-070-4.

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., s. 38.

 Kapanış problemi 
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.

 Yol algoritmaları 
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 
 Çizelgeleme 

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.Skiena, Steven Sol (2009). The Algorithm Design Manual. Springer. s. 469. ISBN 978-1-84800-070-4. 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. Ö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. Benzer görev sıralama sorunları, bir yazılımın derlenmesinde kullanılan Makefile dosyalarında ve düşük seviyeli programların optimize edilmesinde komut çizelgeleme işlemlerinde de ortaya çıkar.

küçükresim|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.

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.

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. 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.

 Veri işleme ağları 
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. 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 

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. Ö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.. 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. 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. Ö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.

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 
küçükresim|upright=1.5|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.

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.

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.

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.

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ı ’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, ’yu içeren üçgene geçilir. Bu yolun sonunda ulaşılan üçgen, ’yu içeren Delaunay üçgenidir.

 Alıntı grafikleri 

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. Price daha sonra bu tür atıf ağları için ilk matematiksel modeli, Price modelini geliştirmiştir.

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.

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: .

 Veri sıkıştırma 
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.

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.

Aynı yol ailesini temsil etmek için DAG kullanma fikri, İkili Karar Diyagramı'nda (İKD) 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 ’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.

 Dış bağlantılar 

DAGitty – DAG (Döngüsüz Yönlü Grafik) oluşturmak için çevrimiçi bir araç

Dipnotlar

 Kaynakça 

Kategori:Matematik
Kategori:Bilgisayar bilimi