Орієнтований граф (коротко орграф) — (мульти)граф, ребрам якого присвоєно напрямок. Орієнтовані ребра називаються також дугами, а в деяких джерелах (Оре) і просто ребрами.
Основні поняття
Формально, орграф D = (V, E) є множина E впорядкованих пар вершин .
Дуга {u, v} інцидентна до вершин u і v. При цьому говорять, що u — початкова вершина дуги, а v — кінцева вершина.
Орграф, отриманий з (простого графу) орієнтацією ребер, називається орієнтованим. На відміну від останнього, у довільного простого орграфу дві вершини можуть з'єднуватися двома різноорієнтованими дугами.
Орієнтований повний граф називається турніром.
Зв'язність
Маршрутом орграфу називають послідовність вершин і дуг, виду (вершини можуть повторюватися). Довжина маршруту — кількість дуг у ньому.
Шлях — маршрут орграфу без повторюваних дуг, простий шлях — без повторюваних вершин. Якщо існує шлях з однієї вершини в іншу, то друга вершина досяжна з першої.
Контур — замкнений шлях.
Для напівмаршруту знімається обмеження на напрямок дуг, аналогічно визначаються напівшлях і напівконтур.
Орграф сильно зв'язний, або просто сильний, якщо всі його вершини взаємно досяжні; Односторонньо зв'язний, або просто односторонній якщо для будь-яких двох вершин, принаймні одна досяжна з іншою; Слабо зв'язний, або просто слабкий, якщо при ігноруванні напрямів дуг виходить зв'язний (мульти)граф;
Максимальний сильний називається сильною компонентою; одностороння компонента і слабка компонента визначаються аналогічно .
Конденсацією орграфу D називають орграф D*, вершинами якого служать сильні компоненти D, а дуга в D* показує наявність хоча б однієї дуги між вершинами, що входять у відповідні компоненти.
Додаткові визначення
Орієнтований ациклічний граф або «гамак» є безконтурним орграфом.
Орієнтований граф, що отриманий із заданого зміною напрямку ребер на протилежні, називається зворотним.
Зображення і властивості всіх орграфів з трьома вузлами
Легенда: С — слабкий, ОС — односторонній, СС — сильний, Н — орієнтований граф, Г — гамак, Т — турніром.
0 дуг | 1 дуга | 2 дуги | 3 дуги | 4 дуги | 5 дуг | 6 дуг |
порожній, Н, Г | Н, Г | ОС | CC | CC | повний, CC | |
---|---|---|---|---|---|---|
ОС, Н, Г | CC, Н, Т | CC | ||||
C, Н, Г | ОС, Н, Г, Т | ОС | ||||
C, Н, Г | ОС | ОС |
Застосування орграфів
Орграф широко застосовуються в програмуванні як спосіб опису систем зі складними зв'язками. Наприклад, одна з основних структур, що використовуються при розробці компіляторів і взагалі для подання комп'ютерних програм — граф потоків даних.
Бінарні відношення
Бінарне відношення над скінченним носієм може бути представлене у вигляді орграфу. Простим орграфом можна представити антирефлексивні відношення, в загальному випадку потрібен орграф з петлями. Якщо відношення симетричне, то його можна представити неорієнтованим графом, а якщо антисиметричне, то орієнтованим графом.
Див. також
Примітки
Література
- Харари Ф. Теория графов — М.: УРСС, 2003. — 300 с. — .
- Оре, Ойстин Теория графов — М.: УРСС, 2008. — 352 с. — .
- Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман Компиляторы: принципы, технологии и инструменты, 2 издание = Compilers: Principles, Techniques, and Tools — 2 изд. — М.: «Вильямс», 2008. — .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Oriyentovanij graf korotko orgraf multi graf rebram yakogo prisvoyeno napryamok Oriyentovani rebra nazivayutsya takozh dugami a v deyakih dzherelah Ore i prosto rebrami Oriyentovanij graf z troma dugami i troma vershinami Osnovni ponyattyaFormalno orgraf D V E ye mnozhina E vporyadkovanih par vershin v V displaystyle v in V Duga u v incidentna do vershin u i v Pri comu govoryat sho u pochatkova vershina dugi a v kinceva vershina Orgraf otrimanij z prostogo grafu oriyentaciyeyu reber nazivayetsya oriyentovanim Na vidminu vid ostannogo u dovilnogo prostogo orgrafu dvi vershini mozhut z yednuvatisya dvoma riznooriyentovanimi dugami Oriyentovanij povnij graf nazivayetsya turnirom Zv yaznist Marshrutom orgrafu nazivayut poslidovnist vershin i dug vidu v 0 v 0 v 1 v 1 v 1 v 2 v 2 v n displaystyle v 0 v 0 v 1 v 1 v 1 v 2 v 2 v n vershini mozhut povtoryuvatisya Dovzhina marshrutu kilkist dug u nomu Shlyah marshrut orgrafu bez povtoryuvanih dug prostij shlyah bez povtoryuvanih vershin Yaksho isnuye shlyah z odniyeyi vershini v inshu to druga vershina dosyazhna z pershoyi Kontur zamknenij shlyah Dlya napivmarshrutu znimayetsya obmezhennya na napryamok dug analogichno viznachayutsya napivshlyah i napivkontur Orgraf silno zv yaznij abo prosto silnij yaksho vsi jogo vershini vzayemno dosyazhni Odnostoronno zv yaznij abo prosto odnostoronnij yaksho dlya bud yakih dvoh vershin prinajmni odna dosyazhna z inshoyu Slabo zv yaznij abo prosto slabkij yaksho pri ignoruvanni napryamiv dug vihodit zv yaznij multi graf Maksimalnij silnij nazivayetsya silnoyu komponentoyu odnostoronnya komponenta i slabka komponenta viznachayutsya analogichno Kondensaciyeyu orgrafu D nazivayut orgraf D vershinami yakogo sluzhat silni komponenti D a duga v D pokazuye nayavnist hocha b odniyeyi dugi mizh vershinami sho vhodyat u vidpovidni komponenti Dodatkovi viznachennya Oriyentovanij aciklichnij graf abo gamak ye bezkonturnim orgrafom Oriyentovanij graf sho otrimanij iz zadanogo zminoyu napryamku reber na protilezhni nazivayetsya zvorotnim Zobrazhennya i vlastivosti vsih orgrafiv z troma vuzlami Legenda S slabkij OS odnostoronnij SS silnij N oriyentovanij graf G gamak T turnirom 0 dug 1 duga 2 dugi 3 dugi 4 dugi 5 dug 6 dug porozhnij N G N G OS CC CC povnij CC OS N G CC N T CC C N G OS N G T OS C N G OS OSZastosuvannya orgrafivOrgraf shiroko zastosovuyutsya v programuvanni yak sposib opisu sistem zi skladnimi zv yazkami Napriklad odna z osnovnih struktur sho vikoristovuyutsya pri rozrobci kompilyatoriv i vzagali dlya podannya komp yuternih program graf potokiv danih Binarni vidnoshennya Orgraf vidnoshennya podilnosti Binarne vidnoshennya nad skinchennim nosiyem mozhe buti predstavlene u viglyadi orgrafu Prostim orgrafom mozhna predstaviti antirefleksivni vidnoshennya v zagalnomu vipadku potriben orgraf z petlyami Yaksho vidnoshennya simetrichne to jogo mozhna predstaviti neoriyentovanim grafom a yaksho antisimetrichne to oriyentovanim grafom Div takozhSlovnik terminiv teoriyi grafiv Oriyentaciya teoriya grafiv VebgrafPrimitkiLiteraturaHarari F Teoriya grafov M URSS 2003 300 s ISBN 5 354 00301 6 Ore Ojstin Teoriya grafov M URSS 2008 352 s ISBN 978 5 397 00044 4 Alfred V Aho Monika S Lam Ravi Seti Dzheffri D Ulman Kompilyatory principy tehnologii i instrumenty 2 izdanie Compilers Principles Techniques and Tools 2 izd M Vilyams 2008 ISBN 978 5 8459 1349 4