Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Орієнта ція неорієнтованого графа це призначення напрямків кожному ребру що перетворює початковий граф на орієнтований г

Орієнтація (теорія графів)

Орієнтація (теорія графів)

Орієнта́ція неорієнтованого графа — це призначення напрямків кожному ребру, що перетворює початковий граф на орієнтований граф.

Орієнтовані графи

Орієнтований граф називають напрямленим, якщо жодна з його пар вершин не з'єднана двома симетричними (різноспрямованими) ребрами. Серед орієнтованих графів ці графи вирізняються відсутністю 2-циклів (тобто граф може містити тільки одну з дуг (x, y) і (y, x)).

Турнір — це орієнтація повного графа. [en] — це орієнтація неорієнтованого дерева. Гіпотеза Самнера стверджує, що будь-який турнір із image вершинами містить будь-яке полідерево з n вершинами.

Число неізоморфних напрямлених графів з n вершинами (для n=1, 2, 3, …) дорівнює

1; 2; 7; 42; 582; 21,480; 2,142,288; 575,016,219; 415,939,243,032; … (послідовність A001174 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

Напрямлені графи перебувають в один-до-одного відповідності з повними орієнтованими графами (графами, в яких є орієнтована дуга між будь-якою парою різних вершин). Повний орієнтований граф можна перетворити в напрямлений граф видаленням усіх 2-циклів, і навпаки, напрямлений граф можна перетворити на повний орієнтований граф додаванням 2-циклу між кожною парою вершин, які не є кінцями якоїсь дуги. Ця відповідність бієктивна. Тому та ж послідовність чисел розв'язує задачу перерахування графів для повних орграфів. Існує явна, але складна формула для чисел цієї послідовності.

Обмежені орієнтації

Сильна орієнтація — це орієнтація, внаслідок якої отримуємо сильно зв'язний орграф. Тісно зв'язані цілком циклічні орієнтації — це орієнтації, в яких кожна дуга належить принаймні одному простому циклу. Орієнтація неорієнтованого графа G цілком циклічна тоді й лише тоді, коли вона є сильною орієнтацією будь-якої компоненти зв'язності графа G. Теорема Роббінса каже, що граф має сильну орієнтацію тоді й лише тоді, коли він реберно 2-зв'язний. Незв'язні графи можуть мати цілком циклічні орієнтації, але тільки в разі, коли в них немає моста.

 — це орієнтація, що приводить до орієнтованого ациклічного графа. Будь-який граф має ациклічну орієнтацію. Всі ациклічні орієнтації можна отримати, розташувавши вершини в ряд, а потім спрямовуючи дугу з ранішої вершини в пізнішу в цьому ряду. стверджує, що граф має ациклічну орієнтацію, в якій найдовший шлях має максимум k вершин, тоді й лише тоді, коли його можна розфарбувати максимум у k кольорів. Ациклічні орієнтації і циклічні орієнтації пов'язані між собою планарною двоїстістю. Ациклічну орієнтацію з єдиним джерелом та єдиним стоком називають .

Транзитивна орієнтація — це орієнтація, за якої одержуваний орієнтований граф є своїм транзитивним замиканням. Графи з транзитивними орієнтаціями називають графами порівнянності. Їх можна визначити з частково впорядкованої множини, якщо зробити два елементи суміжними у всіх випадках, коли вони порівнянні в частковому порядку. Транзитивну орієнтацію, якщо вона існує, можна знайти за лінійний час. Однак перевірка, чи отримана орієнтація (або будь-яка задана орієнтація) дійсно транзитивна, вимагає більше часу, оскільки вона за складністю еквівалентна множенню матриць.

Ейлерова орієнтація неорієнтованого графа — це орієнтація, в якій кожна вершина має однаковий напівстепінь входу і напівстепінь виходу. Ейлерова орієнтація решітки з'являється в статистичній механіці в теорії [en].

має властивість, що певні цикли парної довжини в графі мають непарне число дуг у двох різних напрямках. Такі орієнтації завжди існують для планарних графів, але не завжди для інших типів графів. Ця орієнтація використовується в підрахунку досконалих парувань.

Примітки

  1. Diestel, 2005.
  2. Слід зауважити, що в російському перекладі книги Дістеля «oriented» перекладається як «направленный» (спрямований), а «directed» — як «ориентированный» (орієнтований), тобто поняття переставлено місцями. Це може спричинити плутанину. В цій статті, як і в інших статтях Вікіпедії, прийнято визначення з російського перекладу.
  3. Rebane, Pearl, 1987, с. 222–228.
  4. Sumner's Universal Tournament Conjecture [ 27 лютого 2014 у Wayback Machine.], Douglas B. West, retrieved 2012-08-02.
  5. Harary, Palmer, 1973, с. 133.
  6. Robbins, 1939, с. 281–283.
  7. Nešetřil, Ossona de Mendez, 2012, с. 42.
  8. de Fraysseix, Ossona de Mendez, Rosenstiehl, 1995, с. 157–179.
  9. Ghouila-Houri, 1962, с. 1370–1371.
  10. McConnell, Spinrad, 1997, с. 19–25.
  11. Mihail, Winkler, 1992, с. 138–145.
  12. Thomas, 2006, с. 963–984.

Література

  • Reinhard Diestel. 1.10 Other notions of graphs // [1] — 3rd. — , 2005. — . з джерела 20 листопада 2021 Перевод:
    • Рейнгард Дистель. 1.10 Другие виды графов // Теория графов. — Новосибирск : Издательство Института математики, 2002. — УДК 519.17 ББЛ 22.17.
  • George Rebane, Judea Pearl. The recovery of causal poly-trees from statistical data // Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987. — 1987. — С. 222–228.[недоступне посилання з Май 2019]
  • Frank Harary, Edgar M. Palmer. Formula 5.4.13 // Graphical Enumeration. — New York : Academic Press, 1973. — С. 133. Перевод:
    • Ф. Харари, Э. Палмер. Формула 5.4.13 // Перечисление графов. — М. : Мир, 1977. — С. 163.
  • Robbins H. E. A theorem on graphs, with an application to a problem of traffic control // The American Mathematical Monthly. — 1939. — Т. 46, вип. 5 (16 червня). — С. 281–283. — DOI:10.2307/2303897.
  • Jaroslav Nešetřil, Patrice Ossona de Mendez. Theorem 3.13 // Sparsity: Graphs, Structures, and Algorithms. — Heidelberg : Springer, 2012. — Т. 28. — С. 42. — (Algorithms and Combinatorics) — . — DOI:10.1007/978-3-642-27875-4.
  • Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre Rosenstiehl. Bipolar orientations revisited // Discrete Applied Mathematics. — 1995. — Т. 56, вип. 2–3 (16 червня). — С. 157–179. — DOI:10.1016/0166-218X(94)00085-R.
  • Alain Ghouila-Houri. Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre // . — 1962. — Т. 254 (16 червня). — С. 1370–1371.
  • McConnell R. M., Spinrad J. Linear-time transitive orientation // 8th ACM-SIAM Symposium on Discrete Algorithms. — 1997. — С. 19–25.
  • Milena Mihail, Peter Winkler. On the Number of Eularian Orientations of a Graph // Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms. — Philadelphia, PA, USA : Society for Industrial and Applied Mathematics, 1992. — С. 138–145. — (SODA '92) — .
  • Robin Thomas (mathematician). A survey of Pfaffian orientations of graphs // International Congress of Mathematicians. Vol. III. — Eur. Math. Soc., Zürich, 2006. — С. 963–984. — DOI:10.4171/022-3/47.

Посилання

  • Weisstein, Eric W. Орієнтація графа(англ.) на сайті Wolfram MathWorld.
  • Weisstein, Eric W. Орієнтований граф(англ.) на сайті Wolfram MathWorld.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Oriyenta ciya neoriyentovanogo grafa ce priznachennya napryamkiv kozhnomu rebru sho peretvoryuye pochatkovij graf na oriyentovanij graf Oriyentovani grafiOriyentovanij graf nazivayut napryamlenim yaksho zhodna z jogo par vershin ne z yednana dvoma simetrichnimi riznospryamovanimi rebrami Sered oriyentovanih grafiv ci grafi viriznyayutsya vidsutnistyu 2 cikliv tobto graf mozhe mistiti tilki odnu z dug x y i y x Turnir ce oriyentaciya povnogo grafa en ce oriyentaciya neoriyentovanogo dereva Gipoteza Samnera stverdzhuye sho bud yakij turnir iz 2 n 2 displaystyle 2n 2 vershinami mistit bud yake poliderevo z n vershinami Chislo neizomorfnih napryamlenih grafiv z n vershinami dlya n 1 2 3 dorivnyuye 1 2 7 42 582 21 480 2 142 288 575 016 219 415 939 243 032 poslidovnist A001174 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Napryamleni grafi perebuvayut v odin do odnogo vidpovidnosti z povnimi oriyentovanimi grafami grafami v yakih ye oriyentovana duga mizh bud yakoyu paroyu riznih vershin Povnij oriyentovanij graf mozhna peretvoriti v napryamlenij graf vidalennyam usih 2 cikliv i navpaki napryamlenij graf mozhna peretvoriti na povnij oriyentovanij graf dodavannyam 2 ciklu mizh kozhnoyu paroyu vershin yaki ne ye kincyami yakoyis dugi Cya vidpovidnist biyektivna Tomu ta zh poslidovnist chisel rozv yazuye zadachu pererahuvannya grafiv dlya povnih orgrafiv Isnuye yavna ale skladna formula dlya chisel ciyeyi poslidovnosti Obmezheni oriyentaciyiSilna oriyentaciya ce oriyentaciya vnaslidok yakoyi otrimuyemo silno zv yaznij orgraf Tisno zv yazani cilkom ciklichni oriyentaciyi ce oriyentaciyi v yakih kozhna duga nalezhit prinajmni odnomu prostomu ciklu Oriyentaciya neoriyentovanogo grafa G cilkom ciklichna todi j lishe todi koli vona ye silnoyu oriyentaciyeyu bud yakoyi komponenti zv yaznosti grafa G Teorema Robbinsa kazhe sho graf maye silnu oriyentaciyu todi j lishe todi koli vin reberno 2 zv yaznij Nezv yazni grafi mozhut mati cilkom ciklichni oriyentaciyi ale tilki v razi koli v nih nemaye mosta ce oriyentaciya sho privodit do oriyentovanogo aciklichnogo grafa Bud yakij graf maye aciklichnu oriyentaciyu Vsi aciklichni oriyentaciyi mozhna otrimati roztashuvavshi vershini v ryad a potim spryamovuyuchi dugu z ranishoyi vershini v piznishu v comu ryadu stverdzhuye sho graf maye aciklichnu oriyentaciyu v yakij najdovshij shlyah maye maksimum k vershin todi j lishe todi koli jogo mozhna rozfarbuvati maksimum u k koloriv Aciklichni oriyentaciyi i ciklichni oriyentaciyi pov yazani mizh soboyu planarnoyu dvoyististyu Aciklichnu oriyentaciyu z yedinim dzherelom ta yedinim stokom nazivayut Tranzitivna oriyentaciya ce oriyentaciya za yakoyi oderzhuvanij oriyentovanij graf ye svoyim tranzitivnim zamikannyam Grafi z tranzitivnimi oriyentaciyami nazivayut grafami porivnyannosti Yih mozhna viznachiti z chastkovo vporyadkovanoyi mnozhini yaksho zrobiti dva elementi sumizhnimi u vsih vipadkah koli voni porivnyanni v chastkovomu poryadku Tranzitivnu oriyentaciyu yaksho vona isnuye mozhna znajti za linijnij chas Odnak perevirka chi otrimana oriyentaciya abo bud yaka zadana oriyentaciya dijsno tranzitivna vimagaye bilshe chasu oskilki vona za skladnistyu ekvivalentna mnozhennyu matric Ejlerova oriyentaciya neoriyentovanogo grafa ce oriyentaciya v yakij kozhna vershina maye odnakovij napivstepin vhodu i napivstepin vihodu Ejlerova oriyentaciya reshitki z yavlyayetsya v statistichnij mehanici v teoriyi en maye vlastivist sho pevni cikli parnoyi dovzhini v grafi mayut neparne chislo dug u dvoh riznih napryamkah Taki oriyentaciyi zavzhdi isnuyut dlya planarnih grafiv ale ne zavzhdi dlya inshih tipiv grafiv Cya oriyentaciya vikoristovuyetsya v pidrahunku doskonalih paruvan PrimitkiDiestel 2005 Slid zauvazhiti sho v rosijskomu perekladi knigi Distelya oriented perekladayetsya yak napravlennyj spryamovanij a directed yak orientirovannyj oriyentovanij tobto ponyattya perestavleno miscyami Ce mozhe sprichiniti plutaninu V cij statti yak i v inshih stattyah Vikipediyi prijnyato viznachennya z rosijskogo perekladu Rebane Pearl 1987 s 222 228 Sumner s Universal Tournament Conjecture 27 lyutogo 2014 u Wayback Machine Douglas B West retrieved 2012 08 02 Harary Palmer 1973 s 133 Robbins 1939 s 281 283 Nesetril Ossona de Mendez 2012 s 42 de Fraysseix Ossona de Mendez Rosenstiehl 1995 s 157 179 Ghouila Houri 1962 s 1370 1371 McConnell Spinrad 1997 s 19 25 Mihail Winkler 1992 s 138 145 Thomas 2006 s 963 984 LiteraturaReinhard Diestel 1 10 Other notions of graphs 1 3rd Springer 2005 ISBN 3 540 26182 6 z dzherela 20 listopada 2021 Perevod Rejngard Distel 1 10 Drugie vidy grafov Teoriya grafov Novosibirsk Izdatelstvo Instituta matematiki 2002 ISBN 5 86134 101 X UDK 519 17 BBL 22 17 George Rebane Judea Pearl The recovery of causal poly trees from statistical data Proc 3rd Annual Conference on Uncertainty in Artificial Intelligence UAI 1987 Seattle WA USA July 1987 1987 S 222 228 nedostupne posilannya z Maj 2019 Frank Harary Edgar M Palmer Formula 5 4 13 Graphical Enumeration New York Academic Press 1973 S 133 Perevod F Harari E Palmer Formula 5 4 13 Perechislenie grafov M Mir 1977 S 163 Robbins H E A theorem on graphs with an application to a problem of traffic control The American Mathematical Monthly 1939 T 46 vip 5 16 chervnya S 281 283 DOI 10 2307 2303897 Jaroslav Nesetril Patrice Ossona de Mendez Theorem 3 13 Sparsity Graphs Structures and Algorithms Heidelberg Springer 2012 T 28 S 42 Algorithms and Combinatorics ISBN 978 3 642 27874 7 DOI 10 1007 978 3 642 27875 4 Hubert de Fraysseix Patrice Ossona de Mendez Pierre Rosenstiehl Bipolar orientations revisited Discrete Applied Mathematics 1995 T 56 vip 2 3 16 chervnya S 157 179 DOI 10 1016 0166 218X 94 00085 R Alain Ghouila Houri Caracterisation des graphes non orientes dont on peut orienter les arretes de maniere a obtenir le graphe d une relation d ordre 1962 T 254 16 chervnya S 1370 1371 McConnell R M Spinrad J Linear time transitive orientation 8th ACM SIAM Symposium on Discrete Algorithms 1997 S 19 25 Milena Mihail Peter Winkler On the Number of Eularian Orientations of a Graph Proceedings of the Third Annual ACM SIAM Symposium on Discrete Algorithms Philadelphia PA USA Society for Industrial and Applied Mathematics 1992 S 138 145 SODA 92 ISBN 0 89791 466 X Robin Thomas mathematician A survey of Pfaffian orientations of graphs International Congress of Mathematicians Vol III Eur Math Soc Zurich 2006 S 963 984 DOI 10 4171 022 3 47 PosilannyaWeisstein Eric W Oriyentaciya grafa angl na sajti Wolfram MathWorld Weisstein Eric W Oriyentovanij graf angl na sajti Wolfram MathWorld

Дата публікації:
Топ