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

Сильна орієнтація неорієнтованого графа це призначення напрямків кожному ребру орієнтація графа за якого граф перетворює

Сильна орієнтація (теорія графів)

Сильна орієнтація (теорія графів)

Сильна орієнтація неорієнтованого графа — це призначення напрямків кожному ребру (орієнтація графа), за якого граф перетворюється на сильно зв'язний граф.

Сильні орієнтації можна використати для планування односторонньої мережі доріг. Згідно з теоремою Роббінса, графи з сильними орієнтаціями — це точно графи без мостів. Ейлерова орієнтація і добре збалансована орієнтація є важливими частковими випадками сильних орієнтацій. У свою чергу, сильні орієнтації можна узагальнити до цілком циклічних орієнтацій незв'язних графів. Множина сильних орієнтацій графа утворює частковий куб, у якому суміжні орієнтації відрізняються лише орієнтацією однієї дуги. Окрему сильну орієнтацію можна знайти за лінійний час, але порахувати число сильних орієнтацій даного графа є #P-повною задачею.

Застосування в регулюванні руху

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

Після роботи Роббінса, в серії статей Робертс і Су (Xu) докладніше промоделювали задачу переведення решітки двосторонніх вулиць міста в односторонні вулиці і досліджували вплив цих переведень на відстані між парами точок у решітці. Як вони показали, традиційний розподіл односторонніх вулиць, за якого напрямок руху паралельними вулицями чергується, не є оптимальним для попарних відстаней. Однак покращена орієнтація, яку вони знайшли, містить точки, де напрямки стикаються (на перехрестя приходить рух з двох протилежних напрямків), що можна розглядати як недолік їхніх розв'язків.

Пов'язані типи орієнтацій

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

Теорема Неша — Вільямса стверджує, що будь-який неорієнтований граф G має добре збалансовану орієнтацію. Це орієнтація, в якій для будь-яких двох вершин u і v графа G число попарно неперетинних (по дугах) орієнтованих шляхів з u до v в отриманому орієнтованому графі дорівнює, щонайменше, image, де k — найбільша кількість шляхів у множині неперетинних (по ребрах) неорієнтованих шляхів з u до v. Орієнтації Неша — Вільямса мають також властивість, що вони дуже близькі до ейлерових орієнтацій — у кожній вершині число вхідних та вихідних дуг відрізняється на одиницю. Із існування добре збалансованих орієнтацій разом з теоремою Менгера негайно випливає теорема Роббінса — за теоремою Менгера реберно двозв'язний граф має щонайменше два неперетинних по ребрах шляхи між будь-якими двома вершинами, звідки випливає, що будь-яка добре збалансована орієнтація має бути сильно зв'язною. З цього результату випливає, що будь-який 2k-реберно-зв'язний неорієнтований граф можна зорієнтувати з утворенням k-реберно-зв'язного орієнтованого графа.

Цілком циклічна орієнтація графа G — це орієнтація, у якій кожне ребро належить орієнтованому циклу. Для зв'язних графів це те саме, що й сильна орієнтація, але цілком циклічну орієнтацію можна визначити для незв'язних графів і це орієнтація, в якій кожна компонента зв'язності графа G стає сильно зв'язною. Теорему Роббінса можна переформулювати, що граф має цілком циклічну орієнтацію тоді й лише тоді, коли в ньому немає мостів. Цілком циклічні орієнтації двоїсті ациклічним орієнтаціям (орієнтації, які перетворюють граф G на орієнтований ациклічний граф) в тому сенсі, що якщо G є планарним, а орієнтації графа G переносяться на орієнтації двоїстого до G планарного графа поворотом ребер на 90°, то цілком циклічна орієнтація графа G відповідає побудованій у такий спосіб ациклічній орієнтації двоїстого графа, і навпаки. Число різних цілком циклічних орієнтацій будь-якого графа G дорівнює image, де image — многочлен Татта графа, а (двоїсте) число ациклічних орієнтацій дорівнює image. Як наслідок, з теореми Роббінса випливає, що многочлен Татта має корінь у точці (0,2) тоді й лише тоді, коли в графі G є міст.

Якщо сильна орієнтація має властивість, що всі орієнтовані цикли проходять через одне ребро st (еквівалентно, якщо зміна орієнтації ребра приводить до ), то ациклічна орієнтація, отримана зміною напряму дуги st, є . В такий спосіб будь-яка біполярна орієнтація пов'язана з сильною орієнтацією.

Граф зміни напрямків дуг

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

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

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

Підрахунок числа сильних орієнтацій даного графа G є #P-повною задачею, навіть коли G планарний і є двочастковим. Однак для щільних графів (точніше, для графів, у яких кожна вершина має лінійне число сусідів), число сильних орієнтацій можна оцінити за допомогою стохастичної схеми наближення до поліноміального часу. Для графів з обмеженою деревною шириною задачу підрахунку сильних орієнтацій можна розв'язати точно за поліноміальний час.

Примітки

  1. Robbins, 1939.
  2. Koh, Tay, 2002.
  3. Schrijver, 1983.
  4. Nash-Williams, 1960.
  5. Nash-Williams, 1969.
  6. Welsh, 1997.
  7. Noy, 2001.
  8. Las Vergnas, 1980.
  9. de Fraysseix, Ossona de Mendez, Rosenstiehl, (1995).
  10. Fukuda, Prodon, Sakuma, 2001.
  11. Див., наприклад, (Atallah, 1984) і (Roberts, 1978).
  12. Arkin, Hassin, 2002.
  13. Vertigan, Welsh, 1992.
  14. Alon, Frieze, Welsh, 1995.

Література

  • Noga Alon, Alan Frieze, Dominic Welsh. Polynomial time randomized approximation schemes for Tutte-Gröthendieck invariants: the dense case // Random Structures & Algorithms. — 1995. — Т. 6, вип. 4. — С. 459–478. — DOI:10.1002/rsa.3240060409.
  • Esther M. Arkin, Refael Hassin. A note on orientations of mixed graphs // Discrete Applied Mathematics. — 2002. — Т. 116, вип. 3. — С. 271–278. — DOI:10.1016/S0166-218X(01)00228-1.
  • Mikhail Atallah. Parallel strong orientation of an undirected graph // . — 1984. — Т. 18, вип. 1. — С. 37–39. — DOI:10.1016/0020-0190(84)90072-3.
  • Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre Rosenstiehl. Bipolar orientations revisited // Discrete Applied Mathematics. — 1995. — Т. 56, вип. 2-3. — С. 157–179. — DOI:10.1016/0166-218X(94)00085-R.
  • Komei Fukuda, Alain Prodon, Tadashi Sakuma. Notes on acyclic orientations and the shelling lemma // Theoretical Computer Science. — 2001. — Т. 263, вип. 1-2. — С. 9–16. — DOI:10.1016/S0304-3975(00)00226-7.[недоступне посилання з Декабрь 2017]
  • K. M. Koh, E. G. Tay. Optimal orientations of graphs and digraphs: a survey // . — 2002. — Т. 18, вип. 4. — С. 745–756. — DOI:10.1007/s003730200060.
  • Michel Las Vergnas. Convexity in oriented matroids // . — 1980. — Т. 29, вип. 2. — С. 231–243. — (Series B). — DOI:10.1016/0095-8956(80)90082-9.
  • C. St. J. A. Nash-Williams. On orientations, connectivity and odd-vertex-pairings in finite graphs. // Canadian Journal of Mathematics. — 1960. — Т. 12. — С. 555–567. — DOI:10.4153/cjm-1960-049-6.
  • C. St. J. A. Nash-Williams. Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968). — New York : Academic Press, 1969. — С. 133–149.
  • Marc Noy. Acyclic and totally cyclic orientations in planar graphs // The American Mathematical Monthly. — 2001. — Т. 108, вип. 1. — С. 66–68. — DOI:10.2307/2695680.
  • H. E. Robbins. A theorem on graphs, with an application to a problem on traffic control // 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)
  • Fred S. Roberts, Yonghua Xu. On the optimal strongly connected orientations of city street graphs. I. Large grids // SIAM Journal on Discrete Mathematics. — 1988. — Т. 1, вип. 2. — С. 199–222. — DOI:10.1137/0401022.
  • Fred S. Roberts, Yonghua Xu. On the optimal strongly connected orientations of city street graphs. II. Two east-west avenues or north-south streets // Networks. — 1989. — Т. 19, вип. 2. — С. 221–233. — DOI:10.1002/net.3230190204.
  • Fred S. Roberts, Yonghua Xu. On the optimal strongly connected orientations of city street graphs. III. Three east-west avenues or north-south streets // Networks. — 1992. — Т. 22, вип. 2. — С. 109–143. — DOI:10.1002/net.3230220202.
  • Fred S. Roberts, Yonghua Xu. On the optimal strongly connected orientations of city street graphs. IV. Four east-west avenues or north-south streets // Discrete Applied Mathematics. — 1994. — Т. 49, вип. 1-3. — С. 331–356. — DOI:10.1016/0166-218X(94)90217-8.
  • A. Schrijver. Bounds on the number of Eulerian orientations // Combinatorica. — 1983. — Т. 3, вип. 3-4. — С. 375–380. — DOI:10.1007/BF02579193.
  • D. L. Vertigan, D. J. A. Welsh. The computational complexity of the Tutte plane: the bipartite case // . — 1992. — Т. 1, вип. 2. — С. 181–187. — DOI:10.1017/S0963548300000195.
  • Dominic Welsh. Surveys in combinatorics, 1997 (London). — Cambridge : Cambridge Univ. Press, 1997. — Т. 241. — С. 287–323. — (London Math. Soc. Lecture Note Ser.) — DOI:10.1017/CBO9780511662119.010.

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

Silna oriyentaciya neoriyentovanogo grafa ce priznachennya napryamkiv kozhnomu rebru oriyentaciya grafa za yakogo graf peretvoryuyetsya na silno zv yaznij graf Silni oriyentaciyi mozhna vikoristati dlya planuvannya odnostoronnoyi merezhi dorig Zgidno z teoremoyu Robbinsa grafi z silnimi oriyentaciyami ce tochno grafi bez mostiv Ejlerova oriyentaciya i dobre zbalansovana oriyentaciya ye vazhlivimi chastkovimi vipadkami silnih oriyentacij U svoyu chergu silni oriyentaciyi mozhna uzagalniti do cilkom ciklichnih oriyentacij nezv yaznih grafiv Mnozhina silnih oriyentacij grafa utvoryuye chastkovij kub u yakomu sumizhni oriyentaciyi vidriznyayutsya lishe oriyentaciyeyu odniyeyi dugi Okremu silnu oriyentaciyu mozhna znajti za linijnij chas ale porahuvati chislo silnih oriyentacij danogo grafa ye P povnoyu zadacheyu Zastosuvannya v regulyuvanni ruhuRobbins zaproponuvav zadachu silnoyi oriyentaciyi z rozpoviddyu pro misto vulici yakogo ta yih peretini podano grafom G Pri comu zhiteli mista hochut mati mozhlivist polagoditi bud yakij segment dorogi v budni dni zberigayuchi mozhlivist distatisya do bud yakoyi chastini mista z bud yakoyi inshoyi chastini po dorogah sho zalishilisya z dvostoronnim ruhom Na vihidnih usi dorogi vidkrivayutsya ale cherez visoku shilnist trafiku zhiteli hochut peretvoryuvati vsi dorogi na odnostoronni zberigayuchi pri comu vlastivist dosyazhnosti bud yakoyi chastini mista z bud yakoyi inshoyi Teorema Robbinsa stverdzhuye sho sistemu dorig mozhna remontuvati v robochi dni todi j lishe todi koli yih mozhna peretvoriti na odnostoronni u vihidni Z ciyeyi prichini teoremu inodi nazivayut teoremoyu odnostoronnih vulic Pislya roboti Robbinsa v seriyi statej Roberts i Su Xu dokladnishe promodelyuvali zadachu perevedennya reshitki dvostoronnih vulic mista v odnostoronni vulici i doslidzhuvali vpliv cih pereveden na vidstani mizh parami tochok u reshitci Yak voni pokazali tradicijnij rozpodil odnostoronnih vulic za yakogo napryamok ruhu paralelnimi vulicyami cherguyetsya ne ye optimalnim dlya poparnih vidstanej Odnak pokrashena oriyentaciya yaku voni znajshli mistit tochki de napryamki stikayutsya na perehrestya prihodit ruh z dvoh protilezhnih napryamkiv sho mozhna rozglyadati yak nedolik yihnih rozv yazkiv Pov yazani tipi oriyentacijYaksho neoriyentovanij graf maye ejleriv cikl ejlerovu oriyentaciya grafa oriyentaciya za yakoyi kozhna vershina maye odnakove chislo vhidnih ta vihidnih dug mozhna znajti zoriyentuvavshi rebra za ejlerovim ciklom Ci oriyentaciyi budut avtomatichno silnimi oriyentaciyami Teorema Nesha Vilyamsa stverdzhuye sho bud yakij neoriyentovanij graf G maye dobre zbalansovanu oriyentaciyu Ce oriyentaciya v yakij dlya bud yakih dvoh vershin u i v grafa G chislo poparno neperetinnih po dugah oriyentovanih shlyahiv z u do v v otrimanomu oriyentovanomu grafi dorivnyuye shonajmenshe k2 displaystyle lfloor frac k 2 rfloor de k najbilsha kilkist shlyahiv u mnozhini neperetinnih po rebrah neoriyentovanih shlyahiv z u do v Oriyentaciyi Nesha Vilyamsa mayut takozh vlastivist sho voni duzhe blizki do ejlerovih oriyentacij u kozhnij vershini chislo vhidnih ta vihidnih dug vidriznyayetsya na odinicyu Iz isnuvannya dobre zbalansovanih oriyentacij razom z teoremoyu Mengera negajno viplivaye teorema Robbinsa za teoremoyu Mengera reberno dvozv yaznij graf maye shonajmenshe dva neperetinnih po rebrah shlyahi mizh bud yakimi dvoma vershinami zvidki viplivaye sho bud yaka dobre zbalansovana oriyentaciya maye buti silno zv yaznoyu Z cogo rezultatu viplivaye sho bud yakij 2k reberno zv yaznij neoriyentovanij graf mozhna zoriyentuvati z utvorennyam k reberno zv yaznogo oriyentovanogo grafa Cilkom ciklichna oriyentaciya grafa G ce oriyentaciya u yakij kozhne rebro nalezhit oriyentovanomu ciklu Dlya zv yaznih grafiv ce te same sho j silna oriyentaciya ale cilkom ciklichnu oriyentaciyu mozhna viznachiti dlya nezv yaznih grafiv i ce oriyentaciya v yakij kozhna komponenta zv yaznosti grafa G staye silno zv yaznoyu Teoremu Robbinsa mozhna pereformulyuvati sho graf maye cilkom ciklichnu oriyentaciyu todi j lishe todi koli v nomu nemaye mostiv Cilkom ciklichni oriyentaciyi dvoyisti aciklichnim oriyentaciyam oriyentaciyi yaki peretvoryuyut graf G na oriyentovanij aciklichnij graf v tomu sensi sho yaksho G ye planarnim a oriyentaciyi grafa G perenosyatsya na oriyentaciyi dvoyistogo do G planarnogo grafa povorotom reber na 90 to cilkom ciklichna oriyentaciya grafa G vidpovidaye pobudovanij u takij sposib aciklichnij oriyentaciyi dvoyistogo grafa i navpaki Chislo riznih cilkom ciklichnih oriyentacij bud yakogo grafa G dorivnyuye TG 0 2 displaystyle T G 0 2 de TG displaystyle T G mnogochlen Tatta grafa a dvoyiste chislo aciklichnih oriyentacij dorivnyuye TG 2 0 displaystyle T G 2 0 Yak naslidok z teoremi Robbinsa viplivaye sho mnogochlen Tatta maye korin u tochci 0 2 todi j lishe todi koli v grafi G ye mist Yaksho silna oriyentaciya maye vlastivist sho vsi oriyentovani cikli prohodyat cherez odne rebro st ekvivalentno yaksho zmina oriyentaciyi rebra privodit do to aciklichna oriyentaciya otrimana zminoyu napryamu dugi st ye V takij sposib bud yaka bipolyarna oriyentaciya pov yazana z silnoyu oriyentaciyeyu Graf zmini napryamkiv dugYaksho graf G 3 reberno zv yaznij a X i Y dvi rizni silni oriyentaciyi grafa G to mozhna peretvoriti X na Y pokrokovo zminyuyuchi oriyentaciyu odniyeyi dugi takim chinom sho na kozhnomu kroci oriyentaciya zalishayetsya silnoyu Takim chinom graf perevertan graf zmini napryamiv dug vershini yakogo vidpovidayut silnim oriyentaciyam grafa G a rebra vidpovidayut param silnih oriyentacij sho vidriznyayutsya napryamkom odnogo rebra utvoryuye chastkovij kub Algoritmi ta skladnistSilnu oriyentaciyu danogo neoriyentovanogo grafa bez mostiv mozhna znajti za linijnij chas zdijsnennyam poshuku v glibinu grafa oriyentuvannyam usih reber pid chas poshuku vid korenya ta oriyentuvannya inshih reber yaki mayut z yednuvati predka ta nashadka v derevi poshuku v glibinu vid nashadka do predka Yaksho dano neoriyentovanij graf G z mostami razom zi spiskom oriyentovanih par vershin yaki mayut buti z yednani oriyentovanimi shlyahami mozhna za polinomialnij chas znajti oriyentaciyu grafa G sho z yednuye vsi zadani pari yaksho vona isnuye Odnak ta sama zadacha ye NP povnoyu yaksho vhid mozhe buti zmishanim grafom Pidrahunok chisla silnih oriyentacij danogo grafa G ye P povnoyu zadacheyu navit koli G planarnij i ye dvochastkovim Odnak dlya shilnih grafiv tochnishe dlya grafiv u yakih kozhna vershina maye linijne chislo susidiv chislo silnih oriyentacij mozhna ociniti za dopomogoyu stohastichnoyi shemi nablizhennya do polinomialnogo chasu Dlya grafiv z obmezhenoyu derevnoyu shirinoyu zadachu pidrahunku silnih oriyentacij mozhna rozv yazati tochno za polinomialnij chas PrimitkiRobbins 1939 Koh Tay 2002 Schrijver 1983 Nash Williams 1960 Nash Williams 1969 Welsh 1997 Noy 2001 Las Vergnas 1980 de Fraysseix Ossona de Mendez Rosenstiehl 1995 Fukuda Prodon Sakuma 2001 Div napriklad Atallah 1984 i Roberts 1978 Arkin Hassin 2002 Vertigan Welsh 1992 Alon Frieze Welsh 1995 LiteraturaNoga Alon Alan Frieze Dominic Welsh Polynomial time randomized approximation schemes for Tutte Grothendieck invariants the dense case Random Structures amp Algorithms 1995 T 6 vip 4 S 459 478 DOI 10 1002 rsa 3240060409 Esther M Arkin Refael Hassin A note on orientations of mixed graphs Discrete Applied Mathematics 2002 T 116 vip 3 S 271 278 DOI 10 1016 S0166 218X 01 00228 1 Mikhail Atallah Parallel strong orientation of an undirected graph 1984 T 18 vip 1 S 37 39 DOI 10 1016 0020 0190 84 90072 3 Hubert de Fraysseix Patrice Ossona de Mendez Pierre Rosenstiehl Bipolar orientations revisited Discrete Applied Mathematics 1995 T 56 vip 2 3 S 157 179 DOI 10 1016 0166 218X 94 00085 R Komei Fukuda Alain Prodon Tadashi Sakuma Notes on acyclic orientations and the shelling lemma Theoretical Computer Science 2001 T 263 vip 1 2 S 9 16 DOI 10 1016 S0304 3975 00 00226 7 nedostupne posilannya z Dekabr 2017 K M Koh E G Tay Optimal orientations of graphs and digraphs a survey 2002 T 18 vip 4 S 745 756 DOI 10 1007 s003730200060 Michel Las Vergnas Convexity in oriented matroids 1980 T 29 vip 2 S 231 243 Series B DOI 10 1016 0095 8956 80 90082 9 C St J A Nash Williams On orientations connectivity and odd vertex pairings in finite graphs Canadian Journal of Mathematics 1960 T 12 S 555 567 DOI 10 4153 cjm 1960 049 6 C St J A Nash Williams Recent Progress in Combinatorics Proc Third Waterloo Conf on Combinatorics 1968 New York Academic Press 1969 S 133 149 Marc Noy Acyclic and totally cyclic orientations in planar graphs The American Mathematical Monthly 2001 T 108 vip 1 S 66 68 DOI 10 2307 2695680 H E Robbins A theorem on graphs with an application to a problem on traffic control 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 Fred S Roberts Yonghua Xu On the optimal strongly connected orientations of city street graphs I Large grids SIAM Journal on Discrete Mathematics 1988 T 1 vip 2 S 199 222 DOI 10 1137 0401022 Fred S Roberts Yonghua Xu On the optimal strongly connected orientations of city street graphs II Two east west avenues or north south streets Networks 1989 T 19 vip 2 S 221 233 DOI 10 1002 net 3230190204 Fred S Roberts Yonghua Xu On the optimal strongly connected orientations of city street graphs III Three east west avenues or north south streets Networks 1992 T 22 vip 2 S 109 143 DOI 10 1002 net 3230220202 Fred S Roberts Yonghua Xu On the optimal strongly connected orientations of city street graphs IV Four east west avenues or north south streets Discrete Applied Mathematics 1994 T 49 vip 1 3 S 331 356 DOI 10 1016 0166 218X 94 90217 8 A Schrijver Bounds on the number of Eulerian orientations Combinatorica 1983 T 3 vip 3 4 S 375 380 DOI 10 1007 BF02579193 D L Vertigan D J A Welsh The computational complexity of the Tutte plane the bipartite case 1992 T 1 vip 2 S 181 187 DOI 10 1017 S0963548300000195 Dominic Welsh Surveys in combinatorics 1997 London Cambridge Cambridge Univ Press 1997 T 241 S 287 323 London Math Soc Lecture Note Ser DOI 10 1017 CBO9780511662119 010

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