| dbo:abstract
|
- توجيه الرسم البياني غير الدوري (بالإنجليزية: Directed acyclic graph)، في الرياضيات، ولا سيما نظرية الرسم البياني وعلوم الكمبيوتر، الرسم البياني غير الدوري الموجه (DAG أو dag / ˈdæɡ / (حول هذا الصوت)) هو رسم بياني موجه بدون دورات موجهة. أي أنه يتكون من الرؤوس والحواف (تسمى أيضًا الأقواس)، مع توجيه كل حافة من رأس إلى آخر، بحيث لا توجد طريقة للبدء من أي قمة v واتباع تسلسل متسق من الحواف التي تتكرر في النهاية ل v مرة أخرى. بالتساوي، DAG هو رسم بياني موجه له ترتيب طوبولوجي، تسلسل من القمم بحيث يتم توجيه كل حافة من وقت سابق إلى لاحقًا في التسلسل. يمكن لـ DAGs نمذجة العديد من أنواع المعلومات المختلفة. على سبيل المثال، يمكن نمذجة جدول بيانات على هيئة DAG ، برأس لكل خلية وحافة عندما تستخدم الصيغة في خلية واحدة القيمة من أخرى؛ يمكن استخدام الترتيب الطوبولوجي لـ DAG هذا لتحديث جميع قيم الخلايا عند تغيير جدول البيانات. وبالمثل، يمكن استخدام الترتيب الطوبولوجي لـ DAGs لطلب عمليات التجميع في ملف makefile. تستخدم تقنية تقييم البرنامج ومراجعته (PERT) DAGs لنمذجة معالم وأنشطة المشاريع البشرية الكبيرة، وجدولة هذه المشاريع لاستخدام أقل وقت إجمالي ممكن. تتضمن الكتل المنطقية التوافقية في تصميم الدوائر الإلكترونية، والعمليات في لغات برمجة تدفق البيانات، شبكات غير دورية لعناصر المعالجة. يمكن أن تمثل DAG أيضًا مجموعات من الأحداث وتأثيرها على بعضها البعض، إما في بنية احتمالية مثل شبكة Bayesian أو كسجل للبيانات التاريخية مثل أشجار العائلة أو تواريخ الإصدارات لأنظمة التحكم في المراجعة الموزعة. يمكن أيضًا استخدام DAGs كتمثيل مضغوط لبيانات التسلسل، مثل تمثيل الرسم البياني للكلمات الحلقية الموجه لمجموعة من السلاسل، أو تمثيل مخطط القرار الثنائي لتسلسل الخيارات الثنائية. بشكل أكثر تجريدًا، تشكل علاقة قابلية الوصول في DAG ترتيبًا جزئيًا، ويمكن تمثيل أي ترتيب جزئي محدود بواسطة DAG باستخدام قابلية الوصول. تتضمن المشكلات الحسابية ذات الوقت متعدد الحدود المهمة في DAGs الفرز الطوبولوجي (حساب الترتيب الطوبولوجي)، وبناء الإغلاق الانتقالي والاختزال الانتقالي (أكبر وأصغر DAGs مع نفس علاقة قابلية الوصول، على التوالي) للمجموعات، ومشكلة الإغلاق، حيث الهدف هو العثور على مجموعة فرعية ذات وزن أدنى من الرؤوس بدون حواف تربطها ببقية الرسم البياني. يعد تحويل الرسم البياني الموجه بالدورات إلى DAG عن طريق حذف أقل عدد ممكن من الرؤوس أو الحواف (مجموعة قمة التغذية المرتدة ومشكلة مجموعة حافة التغذية المرتدة، على التوالي) مشكلة صعبة NP ، ولكن يمكن تحويل أي رسم بياني موجه إلى DAG (التكثيف) عن طريق التعاقد مع كل مكون متصل بقوة في خفة واحدة. يمكن حل مشاكل العثور على أقصر المسارات والمسارات الأطول على DAGs في الوقت الخطي، على عكس الرسوم البيانية التعسفية التي تكون فيها خوارزميات المسار الأقصر أبطأ وأطول مسار مشاكل NP-hard. المفهوم المقابل للرسوم البيانية غير الموجهة هو الغابة، رسم بياني غير موجه بدون دورات. ينتج عن اختيار اتجاه الغابة نوعًا خاصًا من الرسم البياني غير الدوري الموجه يسمى الشجرة المتعددة. ومع ذلك، لا يتوافق كل رسم بياني غير دوري موجه مع اتجاه حواف رسم بياني لا دوري غير موجه. بعد كل شيء، كل رسم بياني غير موجه، سواء كان دوريًا أو غير دوري، له اتجاه لا دوري، وتخصيص لاتجاه لحوافه يجعله في رسم بياني لا دوري موجه. للتأكيد على أن DAGs ليست هي نفس الإصدارات الموجهة من الرسوم البيانية غير الدورية غير الموجهة، يسميها بعض المؤلفين الرسوم البيانية غير الدورية الموجهة [1] أو الرسوم البيانية غير الدورية. (ar)
- En ciències de la computació i matemàtiques un graf acíclic dirigit (o grafo acíclic dirigit ) conegut com a DAG per les seves sigles en anglès, és un graf dirigit que no té cicles; això significa que per a cada vèrtex v , no hi ha un camí directe que comenci i acabi en v . Els DAG apareixen en models on no té sentit que un vèrtex tingui un camí directe a ell mateix, per exemple, si un arc o → v indica que v és part de o , crear un cicle v → o indicaria que o és subconjunt de si mateix i de v , la qual cosa és impossible. Informalment un DAG "flueix" en només una direcció. Cada DAG dona lloc a un ordenament parcial ≤ sobre els seus vèrtexs, on o ≤ v exactament quan hi ha un camí directe des de o a v . Molts DAG poden generar el mateix ordenament parcial dels vèrtexs sent el de menor nombre d'arcs anomenat la reducció transitiva i el que major nombre d'arcs la Cloenda transitiva. En particular, la clausura transitiva és l'ordre d'accessibilitat ≤ . (ca)
- Στην Επιστήμη Υπολογιστών, ένας γράφος ονομάζεται κατευθυνόμενος άκυκλος γράφος αν είναι κατευθυνόμενος και δεν περιέχει κύκλους. Δηλαδή, οι ακμές του δεν είναι αμφίδρομες, αλλά έχουν κατεύθυνση, και για κανένα κόμβο δεν υπάρχει μονοπάτι (πέρα από το τετριμμένο) που να ξεκινά από αυτόν και να καταλήγει σ' αυτόν. Ένας κατευθυνόμενος άκυκλος γράφος μπορεί να χρησιμεύσει στη μοντελοποίηση διαφόρων δομών. Για παράδειγμα, μιας ροής εργασιών, ή ενός προγράμματος σπουδών όπου κάποια μαθήματα έχουν προαπαιτούμενα μαθήματα, ή μιας στα στοιχεία ενός συνόλου. (el)
- In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called arcs), with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology (evolution, family trees, epidemiology) to information science (citation networks) to computation (scheduling). Directed acyclic graphs are sometimes instead called acyclic directed graphs or acyclic digraphs. (en)
- En ciencias de la computación y matemáticas un grafo acíclico dirigido o DAG (del inglés Directed Acyclic Graph), es un grafo dirigido que no tiene ciclos; esto significa que para cada vértice v, no hay un camino directo que empiece y termine en v. Los DAG aparecen en modelos donde no tiene sentido que un vértice tenga un camino directo a él mismo; por ejemplo, si un arco u→v indica que v es parte de u, crear un ciclo v→u indicaría que u es subconjunto de sí mismo y de v, lo cual es imposible. Informalmente un DAG "fluye" en solo una dirección. Cada DAG da lugar a un ordenamiento parcial ≤ sobre sus vértices, donde u ≤ v exactamente cuando existe un camino directo desde u a v. Muchos DAG pueden generar el mismo ordenamiento parcial de los vértices siendo el de menor número de arcos denominado la reducción transitiva y el que mayor número de arcos la Clausura transitiva. En particular, la clausura transitiva es el orden de accesibilidad ≤. (es)
- En théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG), est un graphe orienté qui ne possède pas de circuit. Un tel graphe peut être vu comme une hiérarchie. (fr)
- In matematica e informatica un grafo aciclico diretto oppure grafo aciclico orientato (in inglese Directed acyclic graph, DAG) è un particolare tipo di digrafo (anche noto come "grafo diretto") che non ha cicli (circuiti) diretti, ovvero comunque scegliamo un vertice del grafo non possiamo tornare ad esso percorrendo gli archi del grafo.Un grafo diretto può dirsi aciclico (cioè è un DAG) se una visita in profondità non presenta archi all'indietro. I DAG sono usati per rappresentare diversi tipi di strutture sia in matematica che in informatica. Per esempio una serie di lavori che devono essere ordinati in modo tale che alcuni di essi debbano essere eseguiti prima di altri (per esempio le applicazioni da eseguire durante l'avvio di un computer) possono essere rappresentati con un DAG dove ogni vertice rappresenta un lavoro e ogni arco la relazione di dipendenza, cioè se c'è un arco che va da A a B vuol dire che A deve essere eseguito prima di B; l'algoritmo per l'ordinamento topologico rappresenta una buona soluzione al problema. I DAG possono anche essere usati per rappresentare in modo efficiente una serie di sequenze che si sovrappongono. Fra i grafi non diretti (cioè i grafi nei quali ogni arco può essere percorso in tutte e due le direzioni) il corrispondente del DAG o grafo aciclico è l'albero. (it)
- 유향 비순환 그래프(有向 非循環 graph, directed acyclic graph, DAG) 및 방향 비순환 그래프(方向 非循環 graph)는 수학, 컴퓨터 과학 분야의 용어의 하나로서 방향 순환이 없는 무한 유향 그래프이다. 즉, 무한히 수많은 꼭짓점과 간선으로 구성되며 각 간선은 하나의 꼭짓점에서 다른 꼭짓점으로 방향을 잇는데 이처럼 어떠한 꼭짓점 v에서 시작하여 끝내 다시 v로 돌아가 순환 반복되는 일정한 방향의 일련한 간선을 따라가는 방법이 없다. 다시 말해 DAG는 위상정렬이 있는 유향 그래프이다. DAG는 각기 다른 종류의 수많은 정보를 모델링할 수 있다. 스프레드시트는 DAG로 모델링이 가능한데, 각 셀에 대해서는 꼭짓점으로, 간선의 경우 하나의 셀의 공식이 다른 셀의 값을 사용하는 곳에 쓸 수 있다. 즉, DAG의 위상정렬을 사용하면 스프레드시트가 변경될 때 모든 셀의 값을 업데이트할 수 있다. (ko)
- 有向非巡回グラフ、有向非循環グラフ、有向無閉路グラフ（ゆうこうひじゅんかいグラフ、英: Directed acyclic graph, DAG）とは、グラフ理論における閉路のない有向グラフのことである。有向グラフは頂点と有向辺（方向を示す矢印付きの辺）からなり、辺は頂点同士をつなぐが、ある頂点から出発し、辺をたどり、頂点に戻ってこないのが有向非巡回グラフである。 有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は半順序を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回グラフで表現できる。トポロジカルソートを使うと、妥当な順序を手に入れることができる。加えて、有向非巡回グラフは一部が重なるシーケンスの集合を表現する際の空間効率の良い表現として利用できる。また、有向非巡回グラフはイベント間の因果関係を表現することにも使える。さらに、有向非巡回グラフはデータの流れが一定方向のネットワークを表現することにも使える。 無向グラフにおける対応する概念は森で、森は閉路のない無向グラフである。森から方向を選ぶとpolytreeと呼ばれる特殊な有向非巡回グラフを作ることができる。しかしながら、無向非巡回グラフ（森）に方向付けする方法では作れない有向非巡回グラフがあり、全ての無向グラフはacyclic orientationがあるため、辺に方向付けると有向非巡回グラフになる。この理由から、directed acyclic graphと呼ぶよりもacyclic directed graphと呼ぶ方が正確である。 (ja)
- Skierowany graf acykliczny (ang. directed acyclic graph, DAG) – graf skierowany, który nie posiada cyklów skierowanych. Jest to w informatyce bardzo ważna struktura, łącząca zalety drzew i ogólnych grafów skierowanych. (pl)
- Em matemática, um grafo acíclico dirigido, (em inglês: directed acyclic graph, ou simplesmente um dag ou DAG), é um grafo dirigido sem ciclo; isto é, para qualquer vértice v, não há nenhuma ligação dirigida começando e acabando em v. Estes grafos aparecem em modelos onde não faz sentido que um vértice tenha uma ligação com si próprio. Por exemplo se uma linha u→v indica que v é parte de u, tal ligação indicaria que u é parte de si mesmo, o que é impossível. (pt)
- Спрямований (орієнтований) ациклічний граф (англ. directed acyclic graph, DAG) — випадок орієнтованого графа, в якому відсутні орієнтовані цикли, тобто шляхи, що починаються і закінчуються в одній і тій самій вершині. Орієнтований ациклічний граф є узагальненням дерева (точніше, їх об'єднання — лісу). (uk)
- Ориентированный ациклический граф (направленный ациклический граф, DAG от англ. directed acyclic graph) — орграф, в котором отсутствуют направленные циклы, но могут быть «параллельные» пути, выходящие из одного узла и разными путями приходящие в конечный узел. Направленный ациклический граф является обобщением дерева (точнее, их объединения — леса). Направленные ациклические графы широко используются в приложениях: в компиляторах, в искусственном интеллекте (для представления ), в статистике и машинном обучении (для представления байесовской сети доверия). (ru)
- 在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（DAG，Directed Acyclic Graph）。 因为有向无环图中从一个点到另一个点有可能存在两种路线，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。 (zh)
|
| rdfs:comment
|
- Στην Επιστήμη Υπολογιστών, ένας γράφος ονομάζεται κατευθυνόμενος άκυκλος γράφος αν είναι κατευθυνόμενος και δεν περιέχει κύκλους. Δηλαδή, οι ακμές του δεν είναι αμφίδρομες, αλλά έχουν κατεύθυνση, και για κανένα κόμβο δεν υπάρχει μονοπάτι (πέρα από το τετριμμένο) που να ξεκινά από αυτόν και να καταλήγει σ' αυτόν. Ένας κατευθυνόμενος άκυκλος γράφος μπορεί να χρησιμεύσει στη μοντελοποίηση διαφόρων δομών. Για παράδειγμα, μιας ροής εργασιών, ή ενός προγράμματος σπουδών όπου κάποια μαθήματα έχουν προαπαιτούμενα μαθήματα, ή μιας στα στοιχεία ενός συνόλου. (el)
- En théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG), est un graphe orienté qui ne possède pas de circuit. Un tel graphe peut être vu comme une hiérarchie. (fr)
- 유향 비순환 그래프(有向 非循環 graph, directed acyclic graph, DAG) 및 방향 비순환 그래프(方向 非循環 graph)는 수학, 컴퓨터 과학 분야의 용어의 하나로서 방향 순환이 없는 무한 유향 그래프이다. 즉, 무한히 수많은 꼭짓점과 간선으로 구성되며 각 간선은 하나의 꼭짓점에서 다른 꼭짓점으로 방향을 잇는데 이처럼 어떠한 꼭짓점 v에서 시작하여 끝내 다시 v로 돌아가 순환 반복되는 일정한 방향의 일련한 간선을 따라가는 방법이 없다. 다시 말해 DAG는 위상정렬이 있는 유향 그래프이다. DAG는 각기 다른 종류의 수많은 정보를 모델링할 수 있다. 스프레드시트는 DAG로 모델링이 가능한데, 각 셀에 대해서는 꼭짓점으로, 간선의 경우 하나의 셀의 공식이 다른 셀의 값을 사용하는 곳에 쓸 수 있다. 즉, DAG의 위상정렬을 사용하면 스프레드시트가 변경될 때 모든 셀의 값을 업데이트할 수 있다. (ko)
- Skierowany graf acykliczny (ang. directed acyclic graph, DAG) – graf skierowany, który nie posiada cyklów skierowanych. Jest to w informatyce bardzo ważna struktura, łącząca zalety drzew i ogólnych grafów skierowanych. (pl)
- Em matemática, um grafo acíclico dirigido, (em inglês: directed acyclic graph, ou simplesmente um dag ou DAG), é um grafo dirigido sem ciclo; isto é, para qualquer vértice v, não há nenhuma ligação dirigida começando e acabando em v. Estes grafos aparecem em modelos onde não faz sentido que um vértice tenha uma ligação com si próprio. Por exemplo se uma linha u→v indica que v é parte de u, tal ligação indicaria que u é parte de si mesmo, o que é impossível. (pt)
- Спрямований (орієнтований) ациклічний граф (англ. directed acyclic graph, DAG) — випадок орієнтованого графа, в якому відсутні орієнтовані цикли, тобто шляхи, що починаються і закінчуються в одній і тій самій вершині. Орієнтований ациклічний граф є узагальненням дерева (точніше, їх об'єднання — лісу). (uk)
- Ориентированный ациклический граф (направленный ациклический граф, DAG от англ. directed acyclic graph) — орграф, в котором отсутствуют направленные циклы, но могут быть «параллельные» пути, выходящие из одного узла и разными путями приходящие в конечный узел. Направленный ациклический граф является обобщением дерева (точнее, их объединения — леса). Направленные ациклические графы широко используются в приложениях: в компиляторах, в искусственном интеллекте (для представления ), в статистике и машинном обучении (для представления байесовской сети доверия). (ru)
- 在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（DAG，Directed Acyclic Graph）。 因为有向无环图中从一个点到另一个点有可能存在两种路线，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。 (zh)
- توجيه الرسم البياني غير الدوري (بالإنجليزية: Directed acyclic graph)، في الرياضيات، ولا سيما نظرية الرسم البياني وعلوم الكمبيوتر، الرسم البياني غير الدوري الموجه (DAG أو dag / ˈdæɡ / (حول هذا الصوت)) هو رسم بياني موجه بدون دورات موجهة. أي أنه يتكون من الرؤوس والحواف (تسمى أيضًا الأقواس)، مع توجيه كل حافة من رأس إلى آخر، بحيث لا توجد طريقة للبدء من أي قمة v واتباع تسلسل متسق من الحواف التي تتكرر في النهاية ل v مرة أخرى. بالتساوي، DAG هو رسم بياني موجه له ترتيب طوبولوجي، تسلسل من القمم بحيث يتم توجيه كل حافة من وقت سابق إلى لاحقًا في التسلسل. (ar)
- En ciències de la computació i matemàtiques un graf acíclic dirigit (o grafo acíclic dirigit ) conegut com a DAG per les seves sigles en anglès, és un graf dirigit que no té cicles; això significa que per a cada vèrtex v , no hi ha un camí directe que comenci i acabi en v . Els DAG apareixen en models on no té sentit que un vèrtex tingui un camí directe a ell mateix, per exemple, si un arc o → v indica que v és part de o , crear un cicle v → o indicaria que o és subconjunt de si mateix i de v , la qual cosa és impossible. Informalment un DAG "flueix" en només una direcció. (ca)
- In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called arcs), with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology (evolution, family trees, epidemiology) to information science (citation networks) to computation (scheduling). (en)
- En ciencias de la computación y matemáticas un grafo acíclico dirigido o DAG (del inglés Directed Acyclic Graph), es un grafo dirigido que no tiene ciclos; esto significa que para cada vértice v, no hay un camino directo que empiece y termine en v. Los DAG aparecen en modelos donde no tiene sentido que un vértice tenga un camino directo a él mismo; por ejemplo, si un arco u→v indica que v es parte de u, crear un ciclo v→u indicaría que u es subconjunto de sí mismo y de v, lo cual es imposible. Informalmente un DAG "fluye" en solo una dirección. (es)
- 有向非巡回グラフ、有向非循環グラフ、有向無閉路グラフ（ゆうこうひじゅんかいグラフ、英: Directed acyclic graph, DAG）とは、グラフ理論における閉路のない有向グラフのことである。有向グラフは頂点と有向辺（方向を示す矢印付きの辺）からなり、辺は頂点同士をつなぐが、ある頂点から出発し、辺をたどり、頂点に戻ってこないのが有向非巡回グラフである。 有向非巡回グラフは様々な情報をモデル化するのに使われる。有向非巡回グラフにおける到達可能性は半順序を構成し、全ての有限半順序は到達可能性を利用し有向非巡回グラフで表現可能である。順序づけする必要があるタスクの集合は、あるタスクが他のタスクよりも前に行う必要があるという制約により、頂点をタスク、辺を制約条件で表現すると有向非巡回グラフで表現できる。トポロジカルソートを使うと、妥当な順序を手に入れることができる。加えて、有向非巡回グラフは一部が重なるシーケンスの集合を表現する際の空間効率の良い表現として利用できる。また、有向非巡回グラフはイベント間の因果関係を表現することにも使える。さらに、有向非巡回グラフはデータの流れが一定方向のネットワークを表現することにも使える。 (ja)
- In matematica e informatica un grafo aciclico diretto oppure grafo aciclico orientato (in inglese Directed acyclic graph, DAG) è un particolare tipo di digrafo (anche noto come "grafo diretto") che non ha cicli (circuiti) diretti, ovvero comunque scegliamo un vertice del grafo non possiamo tornare ad esso percorrendo gli archi del grafo.Un grafo diretto può dirsi aciclico (cioè è un DAG) se una visita in profondità non presenta archi all'indietro. (it)
|
