Директан ациклични граф — разлика између измена
Нема описа измене |
м Разне исправке; козметичке измене |
||
| Ред 1: | Ред 1: | ||
{{почетник|30|12|2015}} |
{{почетник|30|12|2015}} |
||
[[Датотека:356px-Directed acyclic graph 3.svg|мини|десно|Пример директног ацикличног графа]] |
[[Датотека:356px-Directed acyclic graph 3.svg|мини|десно|Пример директног ацикличног графа]] |
||
'''Директан ациклилни граф (ДАГ)''' у [[математика|математици]] и [[информатика|информатици]] је директан граф беѕ усмерених циклуса. Састоји се од збира чворова и усмерених грана, свака грана повезује један чвор са другим, тако да не постоји начин да се почне у неком чвору в и прати редослед грана који се на крају петље опет враћа на чвор в. <ref>Christofides, Nicos |
'''Директан ациклилни граф (ДАГ)''' у [[математика|математици]] и [[информатика|информатици]] је директан граф беѕ усмерених циклуса. Састоји се од збира чворова и усмерених грана, свака грана повезује један чвор са другим, тако да не постоји начин да се почне у неком чвору в и прати редослед грана који се на крају петље опет враћа на чвор в. <ref>Christofides, Nicos . Graph theory: an algorithmic approach, Academic Press.. . {{page|year=1975|id=|pages=170}}–174.</ref><ref>Thulasiraman, K.; Swamy, M. N. S. (1992), "5.7 Acyclic Directed Graphs", Graphs: Theory and Algorithms, John Wiley and Son. {{page|year=|isbn=978-0-471-51356-8|pages=}}</ref><ref>Bang-Jensen, Jørgen (2008), "2.1 Acyclic Digraphs", Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics (2nd ed.), Springer-Verlag. pp. 32–34. {{page|year=|isbn=978-1-84800-997-4|pages=118}}</ref> |
||
ДАГ може да се користи за моделирање многих различитих врста информација. Достизање везе у ДАГ форми делимичног реда, и било ког коначно делимичног реда може бити представљен од стране ДАГ који користи достизање. Колекција задатака која се мора одредити у низу, уз ограничење да морају бити извршени одређени задаци раније од других, може бити представљен као ДАГ са чвором за сваки задатак и граном за сваку препреку; алгоритми за [[тополошко уређење]] могу се користити за одређивање исправног низа. Додатно, ДАГ може да се користи као простор ефикасне заступљености низова са преклапајућим поднизовима. ДАГ се такође користи за представљање система догађаја или потенцијалних догађаја и [[узрочност|узрочно–последичих]] односа између њих. ДАГ се такође може користити за моделовање процеса у којима је проток подтака у доследном правцу кроз мрежу процесора, или стања репозиторијума у верзији контоле система. |
ДАГ може да се користи за моделирање многих различитих врста информација. Достизање везе у ДАГ форми делимичног реда, и било ког коначно делимичног реда може бити представљен од стране ДАГ који користи достизање. Колекција задатака која се мора одредити у низу, уз ограничење да морају бити извршени одређени задаци раније од других, може бити представљен као ДАГ са чвором за сваки задатак и граном за сваку препреку; алгоритми за [[тополошко уређење]] могу се користити за одређивање исправног низа. Додатно, ДАГ може да се користи као простор ефикасне заступљености низова са преклапајућим поднизовима. ДАГ се такође користи за представљање система догађаја или потенцијалних догађаја и [[узрочност|узрочно–последичих]] односа између њих. ДАГ се такође може користити за моделовање процеса у којима је проток подтака у доследном правцу кроз мрежу процесора, или стања репозиторијума у верзији контоле система. |
||
| Ред 11: | Ред 11: | ||
=== Достизање, транзитивно затворење, и транзитивна редукција === |
=== Достизање, транзитивно затворење, и транзитивна редукција === |
||
[[Датотека:300px-Hasse diagram of powerset of 3.svg|мини|десно|Хасе дијаграм који представља парцијалан ред ⊆ између подскупова од три елемента скупа.]] |
[[Датотека:300px-Hasse diagram of powerset of 3.svg|мини|десно|Хасе дијаграм који представља парцијалан ред ⊆ између подскупова од три елемента скупа.]] |
||
Сваки усмерени ациклични граф доводи до [[парцијалан ред|парцијалног реда]] ≤ на својим чворовима, где је ''у'' ≤ ''в'' тачно када постоји директан пут од ''у'' до ''в'' у ДАГ.<ref> |
Сваки усмерени ациклични граф доводи до [[парцијалан ред|парцијалног реда]] ≤ на својим чворовима, где је ''у'' ≤ ''в'' тачно када постоји директан пут од ''у'' до ''в'' у ДАГ.<ref>Kozen, Dexter (1992), The Design and Analysis of Algorithms, Monographs in Computer Science, Springer. {{page|year=|isbn=978-0-387-97687-7|pages=}}</ref> Међутим, много различитих ДАГ може довести до тог истог [[достижност]]и односа: <ref>Banerjee, Utpal (1993), "Exercise 2(c)", Loop Transformations for Restructuring Compilers: The Foundations, Springer. pp. 19. {{page|year=|isbn=978-0-7923-9318-4|pages=}}</ref> на пример, ДАГ са две гране ''а'' → ''б'' и ''б'' → ''ц'' има исто достизање као и граф са три гране а → ''б'', ''б'' → ''ц'', и ''а'' → ''ц''. Ако је ''Г'' ДАГ, његова [[транзитивна редукција]] је граф са најмањим бројем грана који представља исто достизање као и за ''Г'', а његово [[транзитивно затворење]] је граф са највише грана који представља исто достизање. Транзитивна редукција и транзитивно затворење су јединствено дефинисани за ДАГ; насупрот томе, за усмерени граф који није ацикличан, не може бити више од једног минимлног подграфа са истим достизањем односа. <ref>Bang-Jensen, Jørgen; Gutin, Gregory Z. (2008), "2.3 Transitive Digraphs, Transitive Closures and Reductions", Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, Springer. pp. 36–39. {{page|year=|isbn=978-1-84800-998-1|pages=9}}</ref> |
||
Транзитивно затварање на ''Г'' има једну грану у → в за сваки везани пар у ≤ в различитих елемената у достизању односа ''Г'', и тако се може посматрати као директан превод достизања односа ≤ у граф - теоријском смислу: сваки парцијални ред скупа може се превести у ДАГ на овај начин. Ако ДАГ ''Г'' представља парцијални ред ≤, онда је [[транзитивна редукција]] од ''Г'' подграф од ''Г'' са једном граном у → в за сваки пар у пропратном односу ≤; [[транзитивна редукција|транзитивне редукције]] су корисне у визуализацији парцијалних редова које они представљају, јер имају мање грана од других графова који представљају исте редове и самим тим доводе до једноставнијих цртежа графова. Хасе дијаграм парцијалног ред је цртеж [[транзитивна редукција|транзитивне редукције]] у којима је оријентација сваке гране приказана тако да је почетни чвор гране на нижем нивоу него његов крајњи чвор. <ref>Jungnickel, Dieter (2012), Graphs, Networks and Algorithms, Algorithms and Computation in Mathematics 5, Springer |
Транзитивно затварање на ''Г'' има једну грану у → в за сваки везани пар у ≤ в различитих елемената у достизању односа ''Г'', и тако се може посматрати као директан превод достизања односа ≤ у граф - теоријском смислу: сваки парцијални ред скупа може се превести у ДАГ на овај начин. Ако ДАГ ''Г'' представља парцијални ред ≤, онда је [[транзитивна редукција]] од ''Г'' подграф од ''Г'' са једном граном у → в за сваки пар у пропратном односу ≤; [[транзитивна редукција|транзитивне редукције]] су корисне у визуализацији парцијалних редова које они представљају, јер имају мање грана од других графова који представљају исте редове и самим тим доводе до једноставнијих цртежа графова. Хасе дијаграм парцијалног ред је цртеж [[транзитивна редукција|транзитивне редукције]] у којима је оријентација сваке гране приказана тако да је почетни чвор гране на нижем нивоу него његов крајњи чвор. <ref>Jungnickel, Dieter (2012), Graphs, Networks and Algorithms, Algorithms and Computation in Mathematics 5, Springer. pp. 92–93. {{page|year=|isbn=978-3-642-32278-5|pages=}}</ref> |
||
=== Тополошко сортирање === |
=== Тополошко сортирање === |
||
Верзија на датум 31. децембар 2015. у 00:01
 | Управо овако су изгледали први чланци неких сада искусних википедијанаца. Почетник треба самостално или уз помоћ других корисника да, након што се упозна са основама уређивања, чланак среди како би се уклопио у стотине хиљада постојећих чланака. Можете да затражите помоћ на Тргу или се обратите за помоћ неком од чланова Википројекта почетнички чланци. Ако имате питања, недоумице и предлоге, користите страницу за разговор. Чланак је означен овим шаблоном 30. 12. 2015. Ако не буде исправљен након седам дана, биће премештен у простор нацрта, на корисничку подстраницу или избрисан. |
Директан ациклилни граф (ДАГ) у математици и информатици је директан граф беѕ усмерених циклуса. Састоји се од збира чворова и усмерених грана, свака грана повезује један чвор са другим, тако да не постоји начин да се почне у неком чвору в и прати редослед грана који се на крају петље опет враћа на чвор в. [1][2][3]
ДАГ може да се користи за моделирање многих различитих врста информација. Достизање везе у ДАГ форми делимичног реда, и било ког коначно делимичног реда може бити представљен од стране ДАГ који користи достизање. Колекција задатака која се мора одредити у низу, уз ограничење да морају бити извршени одређени задаци раније од других, може бити представљен као ДАГ са чвором за сваки задатак и граном за сваку препреку; алгоритми за тополошко уређење могу се користити за одређивање исправног низа. Додатно, ДАГ може да се користи као простор ефикасне заступљености низова са преклапајућим поднизовима. ДАГ се такође користи за представљање система догађаја или потенцијалних догађаја и узрочно–последичих односа између њих. ДАГ се такође може користити за моделовање процеса у којима је проток подтака у доследном правцу кроз мрежу процесора, или стања репозиторијума у верзији контоле система.
Одговарајући концепт неусмерених графова је шума, један неусмерен граф без циклуса. Избор оријентације за шуме производи посебну врсту директног ацикличног графа који се зове оријентисано стабло. Међутим, постоје многе друге врсте директног ацикличног графа које нису формиране прем оријентацији грана једног неусмереног ацикличног графа. Осим тога, сваки неусмерени граф има ацикличну оријентацију, доделу правца за своје гране које га чине директним ацикличним графом. Из тих разлога било би прецизније назвати директан ациклични граф ацикличан усмерени граф или ацикличан диграф.
Математичка својства
Достизање, транзитивно затворење, и транзитивна редукција
Сваки усмерени ациклични граф доводи до парцијалног реда ≤ на својим чворовима, где је у ≤ в тачно када постоји директан пут од у до в у ДАГ.[4] Међутим, много различитих ДАГ може довести до тог истог достижности односа: [5] на пример, ДАГ са две гране а → б и б → ц има исто достизање као и граф са три гране а → б, б → ц, и а → ц. Ако је Г ДАГ, његова транзитивна редукција је граф са најмањим бројем грана који представља исто достизање као и за Г, а његово транзитивно затворење је граф са највише грана који представља исто достизање. Транзитивна редукција и транзитивно затворење су јединствено дефинисани за ДАГ; насупрот томе, за усмерени граф који није ацикличан, не може бити више од једног минимлног подграфа са истим достизањем односа. [6]
Транзитивно затварање на Г има једну грану у → в за сваки везани пар у ≤ в различитих елемената у достизању односа Г, и тако се може посматрати као директан превод достизања односа ≤ у граф - теоријском смислу: сваки парцијални ред скупа може се превести у ДАГ на овај начин. Ако ДАГ Г представља парцијални ред ≤, онда је транзитивна редукција од Г подграф од Г са једном граном у → в за сваки пар у пропратном односу ≤; транзитивне редукције су корисне у визуализацији парцијалних редова које они представљају, јер имају мање грана од других графова који представљају исте редове и самим тим доводе до једноставнијих цртежа графова. Хасе дијаграм парцијалног ред је цртеж транзитивне редукције у којима је оријентација сваке гране приказана тако да је почетни чвор гране на нижем нивоу него његов крајњи чвор. [7]
Тополошко сортирање
Сваки директан ациклични граф има тополошко сортирање, тј. редослед чворова је такав да се почетак крајње тачке сваке гране јавља раније у сортирању од краја крајње тачке гране. У принципу, ово сортирање није јединствено.
- ^ Christofides, Nicos . Graph theory: an algorithmic approach, Academic Press.. . 1975. стр. 170.–174.
- ^ Thulasiraman, K.; Swamy, M. N. S. (1992), "5.7 Acyclic Directed Graphs", Graphs: Theory and Algorithms, John Wiley and Son. ISBN 978-0-471-51356-8.
- ^ Bang-Jensen, Jørgen (2008), "2.1 Acyclic Digraphs", Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics (2nd ed.), Springer-Verlag. pp. 32–34. ISBN 978-1-84800-997-4. стр. 118.
- ^ Kozen, Dexter (1992), The Design and Analysis of Algorithms, Monographs in Computer Science, Springer. ISBN 978-0-387-97687-7.
- ^ Banerjee, Utpal (1993), "Exercise 2(c)", Loop Transformations for Restructuring Compilers: The Foundations, Springer. pp. 19. ISBN 978-0-7923-9318-4.
- ^ Bang-Jensen, Jørgen; Gutin, Gregory Z. (2008), "2.3 Transitive Digraphs, Transitive Closures and Reductions", Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, Springer. pp. 36–39. ISBN 978-1-84800-998-1. стр. 9.
- ^ Jungnickel, Dieter (2012), Graphs, Networks and Algorithms, Algorithms and Computation in Mathematics 5, Springer. pp. 92–93. ISBN 978-3-642-32278-5.