Döngüsel olmayan yönelimli grafik
Olarak grafik teorisi , bir yönlendirilmiş asiklik grafiktir (İngilizce asiklik grafik yönlendirilmiş veya DAG ) a, yönlendirilmiş grafik bir sahiptir devre . Böyle bir grafik bir hiyerarşi olarak görülebilir .
Tanım
Döngüsel olmayan yönlendirilmiş grafik, devre içermeyen yönlendirilmiş bir grafiktir .
- Döngüsel olmayan yönlendirilmiş bir grafiği kapsayan bir alt grafiği her zaman bulabiliriz, bu da bir ağaçtır (yani bir orman).
- Asiklik yönlendirilmiş grafikte, erişilebilirlik ilişki R ( u , v ) tarafından tanımlanan “oradan bir yol mevcut u için v ” a, kısmi sipariş ilişkisi . Topolojik sıralama algoritması ile ilgili bir yol olup olmadığını, diğer bir deyişle (sayı mümkün bu sırada uygun bir şekilde, bir asiklik yönlendirilmiş grafik köşe hale u için v grafikte, o zaman sayısı u az daha uzun olduğu ve v ).
- Bu numaralandırma, seviyelere göre gösterimi kolaylaştırır. Yukarıdaki yönlendirilmiş döngüsel olmayan grafik için, köşeler (7, 5, 3) seviye 1'i, (11, 8) seviye 2'yi, (2, 9, 10) seviye 3'ü oluşturur. Yol (3, 8, 11, 2) tarafından empoze edilen 4 seviye.
Algoritmik yönler
- En kısa yolları problemi bir kaynaktan, örneğin bir grafik lineer zamanda çözülebilir.
- Polinom zamanında minimum yol kapsamı bulmak mümkündür , oysa bu herhangi bir yönlendirilmiş grafikte NP-tam bir problemdir .
- Yönlendirilmiş bir grafik verildiğinde, onu döngüsel olmayan bir grafiğe dönüştürmek için her zaman belirli sayıda köşeyi kaldırabiliriz. Böyle bir derleme, köşe tepe noktaları kümesi ( geri besleme tepe noktası kümesi ) olarak adlandırılır. İlişkili algoritmik sorun en az kardinallikleri gibi bir dizi bulmaya dayanmaktadır.
Kullanımlar
Kavram , örneklerini bulduğumuz geleneksel bir analiz aracını resmileştirir :
- proje çizelgeleme, organizasyon şemaları vb. açısından
- Sonuç olarak katmanlarda modelleri olarak OSI modelinin , modeline Bühler (veya Taber - Nida ait) dilin fonksiyonları , psikoloji veya ihtiyaçların piramidin içinde Maslow .
- IOTA güvenli işlemler teknolojisi , temel veri yapısı için, temel veri yapısı için köklü bir ağaca ( "zincirler" kökten yapraklara giden yollardır) sahip olan daha klasik blok zincirinin aksine, döngüsel olmayan yönlendirilmiş bir grafiğe sahiptir . Her işlem, grafiğin bir düğümüdür.
Gelen bilgisayar bilimleri , kavramı temsili için özellikle geçerlidir açısından delilleri organizasyon paylaşmak ile doğal kesinti veya dillerine teorisi için nesne yönelimi türlerinin sınıflandırılması konusunda.
Notlar ve referanslar
-
Sylvie Hamel, " Oriented graphs " , University of Montreal'de
İlgili Makaleler