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-реберно-зв'язні графи. Тобто тоді й лише тоді можна вибрати напрямок кожного ребра неорієнтованого графа G, перетворивши граф на орієнтований граф, у якому існує (орієнтований) шлях з будь-якої вершини в будь-яку іншу вершину, коли граф G зв'язний і не має мостів.

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

image
Вушна декомпозиція графа без мостів. Орієнтація кожного «вуха» в орієнтований шлях або орієнтований цикл робить весь граф сильно зв'язним.

Характеризацію Роббінса графів сильними орієнтаціями можна довести, використовуючи вушну декомпозицію, інструмент, який Роббінс запропонував для цієї мети.

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

З іншого боку, потрібно показати, що будь-який зв'язний граф без мостів можна сильно орієнтувати. Як довів Роббінс, будь-який такий граф має розбиття на послідовність підграфів, званих «вухами», і в цій послідовності перший підграф є циклом, а кожен наступний підграф є шляхом, кінцеві вершини якого належать попереднім «вухам» послідовності. Якщо орієнтувати ребра в кожному «вусі» так, щоб вийшов орієнтований цикл або орієнтований шлях, отримаємо сильну орієнтацію всього графа.

Пов'язані результати

Узагальнення Беша і Тінделла теореми Роббінса на змішані графи показує, що якщо в графі G деякі ребра орієнтовані, а інші не орієнтовані, і граф G для будь-якої пари вершин містить (орієнтований) шлях, що з'єднує ці вершини і не порушує наявних напрямків ребер, то будь-якому неорієнтованому ребру графа G, що не є мостом, можна надати напрямок без зміни зв'язності графа G. Зокрема, неорієнтований граф без мостів можна зробити сильно зв'язним орієнтованим графом за допомогою жадібного алгоритму, який призначає напрямок ребра за крок, зберігаючи існування шляху між будь-якими двома парами вершин. Такий алгоритм не може застрягти в ситуації, коли неможливо вибрати наступний напрямок для дуги.

Алгоритми і складність

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

Примітки

  1. Robbins, 1939.
  2. Gross, Yellen, 2006.
  3. Boesch, Tindell, 1980.
  4. Вішкін (Vishkin, 1985) приписує це спостереження Аталлі (Atallah, 1984), а Балакрішнан (Balakrishnan, 1996) приписує його Робертсу (Roberts, 1978). Але, як зазначили Кларк і Голтон (Clark, Holton, 1991), той самий алгоритм вже з'являвся (з припущенням вершиннї 2-зв'язності замість реберної 2-зв'язності) в основоположній ранній книзі Гопкрофта і Тарджана (Hopcroft, Tarjan, 1973) про пошук у глибину.
  5. Vishkin, 1985.
  6. Soroker, 1988.

Література

  • Mikhail J. Atallah. Parallel strong orientation of an undirected graph // . — 1984. — Т. 18, вип. 1. — С. 37–39. — DOI:10.1016/0020-0190(84)90072-3.
  • V. K.Balakrishnan. Introductory Discrete Mathematics. — Mineola, NY : Dover Publications Inc, 1996. — С. 135. — .
  • Frank Boesch, Ralph Tindell. Robbins's theorem for mixed multigraphs // The American Mathematical Monthly. — 1980. — Т. 87, вип. 9. — С. 716–719. — DOI:10.2307/2321858.
  • John Clark, Derek Allan Holton. A first look at graph theory. — Teaneck, NJ : World Scientific Publishing Co. Inc, 1991. — С. 254–260. — .
  • Jonathan L. Gross, Jay Yellen. Graph Theory and its Applications. — 2nd. — Boca Raton, FL : Chapman & Hall/CRC, 2006. — С. 498–499. — (Discrete Mathematics and its Applications) — .
  • John Hopcroft, Robert Tarjan. Algorithm 447: efficient algorithms for graph manipulation // Communications of the ACM. — 1973. — Т. 16, вип. 6. — С. 372–378. — DOI:10.1145/362248.362272.
  • H. E. Robbins. A theorem on graphs, with an application to a problem on traffic control // The American Mathematical Monthly. — 1939. — Т. 46. — С. 281–283. — DOI:10.2307/2303897.
  • Fred S. Roberts. Graph Theory and its Applications to Problems of Society. — Philadelphia, Pa. : Society for Industrial and Applied Mathematics (SIAM), 1978. — Т. 29. — С. 7–14. — (CBMS-NSF Regional Conference Series in Applied Mathematics)
  • Danny Soroker. Fast parallel strong orientation of mixed graphs and related augmentation problems // Journal of Algorithms. — 1988. — Т. 9, вип. 2. — С. 205–223. — DOI:10.1016/0196-6774(88)90038-7.
  • Uzi Vishkin. On efficient parallel strong orientation // . — 1985. — Т. 20, вип. 5. — С. 235–240. — DOI:10.1016/0020-0190(85)90025-0..

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

Teore ma Ro bbinsa nazvana na chest amerikanskogo matematika Gerberta Robbinsa stverdzhuye sho grafi yaki mayut silni oriyentaciyi ce tochno 2 reberno zv yazni grafi Tobto todi j lishe todi mozhna vibrati napryamok kozhnogo rebra neoriyentovanogo grafa G peretvorivshi graf na oriyentovanij graf u yakomu isnuye oriyentovanij shlyah z bud yakoyi vershini v bud yaku inshu vershinu koli graf G zv yaznij i ne maye mostiv Oriyentovani grafiVushna dekompoziciya grafa bez mostiv Oriyentaciya kozhnogo vuha v oriyentovanij shlyah abo oriyentovanij cikl robit ves graf silno zv yaznim Harakterizaciyu Robbinsa grafiv silnimi oriyentaciyami mozhna dovesti vikoristovuyuchi vushnu dekompoziciyu instrument yakij Robbins zaproponuvav dlya ciyeyi meti Yaksho v grafi ye mist to jogo ne mozhna silno oriyentuvati oskilki yaku b oriyentaciyu ne obrali nemaye shlyahu z odniyeyi vershini mosta v inshu Z inshogo boku potribno pokazati sho bud yakij zv yaznij graf bez mostiv mozhna silno oriyentuvati Yak doviv Robbins bud yakij takij graf maye rozbittya na poslidovnist pidgrafiv zvanih vuhami i v cij poslidovnosti pershij pidgraf ye ciklom a kozhen nastupnij pidgraf ye shlyahom kincevi vershini yakogo nalezhat poperednim vuham poslidovnosti Yaksho oriyentuvati rebra v kozhnomu vusi tak shob vijshov oriyentovanij cikl abo oriyentovanij shlyah otrimayemo silnu oriyentaciyu vsogo grafa Pov yazani rezultatiUzagalnennya Besha i Tindella teoremi Robbinsa na zmishani grafi pokazuye sho yaksho v grafi G deyaki rebra oriyentovani a inshi ne oriyentovani i graf G dlya bud yakoyi pari vershin mistit oriyentovanij shlyah sho z yednuye ci vershini i ne porushuye nayavnih napryamkiv reber to bud yakomu neoriyentovanomu rebru grafa G sho ne ye mostom mozhna nadati napryamok bez zmini zv yaznosti grafa G Zokrema neoriyentovanij graf bez mostiv mozhna zrobiti silno zv yaznim oriyentovanim grafom za dopomogoyu zhadibnogo algoritmu yakij priznachaye napryamok rebra za krok zberigayuchi isnuvannya shlyahu mizh bud yakimi dvoma parami vershin Takij algoritm ne mozhe zastryagti v situaciyi koli nemozhlivo vibrati nastupnij napryamok dlya dugi Algoritmi i skladnistSilnu oriyentaciyu zadanogo neoriyentovanogo grafa bez mostiv mozhna znajti za linijnij chas poshukom u glibinu za grafom oriyentuyuchi dorogoyu vsi vershini pri prohodi dereva v napryamku vid korenya a reshtu reber vid nashadka do predka Hocha cej algoritm nepridatnij dlya paralelnih obchislyuvalnih sistem vnaslidok skladnosti zdijsnennya na cih komp yuterah poshuku v glibinu isnuyut alternativni algoritmi yaki efektivno rozv yazuyut zadachu v paralelnij modeli obchislen Vidomi takozh paralelni algoritmi dlya poshuku silno zv yaznih oriyentacij dlya zmishanih grafiv PrimitkiRobbins 1939 Gross Yellen 2006 Boesch Tindell 1980 Vishkin Vishkin 1985 pripisuye ce sposterezhennya Atalli Atallah 1984 a Balakrishnan Balakrishnan 1996 pripisuye jogo Robertsu Roberts 1978 Ale yak zaznachili Klark i Golton Clark Holton 1991 toj samij algoritm vzhe z yavlyavsya z pripushennyam vershinnyi 2 zv yaznosti zamist rebernoyi 2 zv yaznosti v osnovopolozhnij rannij knizi Gopkrofta i Tardzhana Hopcroft Tarjan 1973 pro poshuk u glibinu Vishkin 1985 Soroker 1988 LiteraturaMikhail J Atallah Parallel strong orientation of an undirected graph 1984 T 18 vip 1 S 37 39 DOI 10 1016 0020 0190 84 90072 3 V K Balakrishnan Introductory Discrete Mathematics Mineola NY Dover Publications Inc 1996 S 135 ISBN 0 486 69115 2 Frank Boesch Ralph Tindell Robbins s theorem for mixed multigraphs The American Mathematical Monthly 1980 T 87 vip 9 S 716 719 DOI 10 2307 2321858 John Clark Derek Allan Holton A first look at graph theory Teaneck NJ World Scientific Publishing Co Inc 1991 S 254 260 ISBN 981 02 0489 2 Jonathan L Gross Jay Yellen Graph Theory and its Applications 2nd Boca Raton FL Chapman amp Hall CRC 2006 S 498 499 Discrete Mathematics and its Applications ISBN 978 1 58488 505 4 John Hopcroft Robert Tarjan Algorithm 447 efficient algorithms for graph manipulation Communications of the ACM 1973 T 16 vip 6 S 372 378 DOI 10 1145 362248 362272 H E Robbins A theorem on graphs with an application to a problem on traffic control The American Mathematical Monthly 1939 T 46 S 281 283 DOI 10 2307 2303897 Fred S Roberts Graph Theory and its Applications to Problems of Society Philadelphia Pa Society for Industrial and Applied Mathematics SIAM 1978 T 29 S 7 14 CBMS NSF Regional Conference Series in Applied Mathematics Danny Soroker Fast parallel strong orientation of mixed graphs and related augmentation problems Journal of Algorithms 1988 T 9 vip 2 S 205 223 DOI 10 1016 0196 6774 88 90038 7 Uzi Vishkin On efficient parallel strong orientation 1985 T 20 vip 5 S 235 240 DOI 10 1016 0020 0190 85 90025 0

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