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

Перифері йний цикл у неорієнто ваному гра фі цикл який не відокремлює будь яку частину графа від будь якої іншої Перифер

Периферійний цикл

Периферійний цикл

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

image
У цьому графі червоний трикутник, утворений вершинами 1, 2 і 5 є периферійним циклом — інші чотири ребра утворюють окремий міст. Однак, п'ятикутник 1-2-3-4-5 не є периферійним, оскільки два ребра, що залишилися, утворюють два окремих мости.

Визначення

Периферійний цикл image у графі image можна визначити формально одним із таких способів:

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

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

Властивості

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

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

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

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

Пов'язані поняття

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

У матроїдах, нерозділювальний цикл — це цикл матроїда (тобто, мінімальна залежна множина), за якої [en] циклу залишає менший матроїд, який є зв'язним (тобто, який не можна розбити на пряму суму матроїдів). Він аналогічний периферійним циклам, але не тотожний навіть у [en] (матроїди, в яких цикли є простими циклами графа). Наприклад, у повному двочастковому графі image будь-який цикл є периферійним (він має лише один міст, шлях із двох ребер), але графовий матроїд, утворений цим мостом не зв'язний, так що ніякий цикл графового матроїда графа image не є нерозділювальним.

Примітки

  1. Tutte, 1963.
  2. Tutte, 1963, с. 743–767.
  3. Di Battista, Eades, Tamassia, Tollis, 1998, с. 74–75.
  4. Це визначення використав Брун (Bruhn, 2004). Однак, Брун відрізняв випадок, що image має ізольовані вершини, від незв'язності, викликаної видаленням циклу image.
  5. Не плутати з мостом, іншим поняттям з такою ж назвою.
  6. Tutte, 1960, с. 304–320.
  7. Це визначення периферійних циклів спочатку використав Татт(Tutte, 1963). Сеймур і Вівер(Seymour, Weaver, 1984) використали таке саме визначення периферійного циклу, але з іншим визначенням моста, яке нагадує визначення породжених циклів для периферійних циклів.
  8. Див., наприклад, теорему 2.4 у статті Татта (Tutte, 1960), яка показує, що множини вершин мостів пов'язані шляхами, див. статтю Сеймур і Вівера (Seymour, Weaver, 1984) для визначення мостів за допомогою хорд і зв'язних компонент, а також статтю Ді Баттіста, Ідса, Тамассіа, Толліса(Di Battista, Eades, Tamassia, Tollis, 1998) для визначення мостів за допомогою класів еквівалентності бінарного відношення на ребрах.
  9. Tutte, 1963, с. Theorems 2.7 и 2.8.
  10. Див. зауваження після теореми 2.8 у статті Татта (Tutte, 1963). Як зауважив Татт, це було вже відомо Вітні (Whitney, 1932)
  11. Tutte, 1963, с. Theorem 2.5.
  12. Bruhn, 2004, с. 235–256.
  13. Thomassen, Toft, 1981, с. 199–224.
  14. Schmidt, 2014, с. 967—978.
  15. Di Battista, Eades, Tamassia, Tollis, 1998, с. 75–76 Lemma 3.4.
  16. Seymour, Weaver, 1984.
  17. Seymour, Weaver, 1984, с. 241–251.
  18. Див., наприклад, (Borse, Waphare, 2008)
  19. Див., наприклад (Cabello, Mohar, 2007)
  20. Maia, Lemos, Melo, 2007, с. 162–171.

Література

  • Tutte W. T. How to draw a graph // Proceedings of the London Mathematical Society. — 1963. — Т. 13. — С. 743–767. — (Third Series). — DOI:10.1112/plms/s3-13.1.743.
  • Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. — Prentice Hall, 1998. — С. 74–75. — .
  • Tutte W. T. Convex representations of graphs // Proceedings of the London Mathematical Society. — 1960. — Т. 10. — С. 304–320. — (Third Series). — DOI:10.1112/plms/s3-10.1.304.
  • [en]. Non-separable and planar graphs // Transactions of the American Mathematical Society. — 1932. — Т. 34, вип. 2. — С. 339–362. — DOI:10.2307/1989545.
  • Henning Bruhn. The cycle space of a 3-connected locally finite graph is generated by its finite and infinite peripheral circuits // Journal of Combinatorial Theory. — 2004. — Т. 92, вип. 2. — С. 235–256. — (Series B). — DOI:10.1016/j.jctb.2004.03.005.
  • Carsten Thomassen, Bjarne Toft. Non-separating induced cycles in graphs // Journal of Combinatorial Theory. — 1981. — Т. 31, вип. 2. — С. 199–224. — (Series B). — DOI:10.1016/S0095-8956(81)80025-1.
  • Jens M. Schmidt. The Mondshein Sequence // Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14). — 2014. — С. 967—978. — DOI:10.1007/978-3-662-43948-7_80.
  • Seymour P. D., Weaver R. W. A generalization of chordal graphs // Journal of Graph Theory. — 1984. — Т. 8, вип. 2. — С. 241–251. — DOI:10.1002/jgt.3190080206.
  • Borse Y. M., Waphare B. N. Vertex disjoint non-separating cycles in graphs // The Journal of the Indian Mathematical Society. — 2008. — Т. 75, вип. 1—4. — С. 75–92 (2009). — (New Series).
  • Sergio Cabello, Bojan Mohar. Finding shortest non-separating and non-contractible cycles for topologically embedded graphs // . — 2007. — Т. 37, вип. 2. — С. 213–235. — DOI:10.1007/s00454-006-1292-5.
  • Bráulio Maia Junior, Manoel Lemos, Tereza R. B. Melo. Non-separating circuits and cocircuits in matroids // Combinatorics, complexity, and chance. — Oxford : Oxford Univ. Press, 2007. — Т. 34. — С. 162–171. — (Oxford Lecture Ser. Math. Appl.) — DOI:10.1093/acprof:oso/9780198571278.003.0010.

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

Periferi jnij cikl u neoriyento vanomu gra fi cikl yakij ne vidokremlyuye bud yaku chastinu grafa vid bud yakoyi inshoyi Periferijni cikli abo yak yih spochatku nazivali periferijni mnogokutniki oskilki Tatt nazvav cikli mnogokutnikami pershim vivchav Vilyam Tatt Voni vidigrayut vazhlivu rol v opisi planarnih grafiv i v utvorenni prostoriv cikliv neplanarnih grafiv U comu grafi chervonij trikutnik utvorenij vershinami 1 2 i 5 ye periferijnim ciklom inshi chotiri rebra utvoryuyut okremij mist Odnak p yatikutnik 1 2 3 4 5 ne ye periferijnim oskilki dva rebra sho zalishilisya utvoryuyut dva okremih mosti ViznachennyaPeriferijnij cikl C displaystyle C u grafi G displaystyle G mozhna viznachiti formalno odnim iz takih sposobiv C displaystyle C ye periferijnim ciklom yaksho vin ye prostim ciklom u zv yaznomu grafi z vlastivistyu za yakoyi dlya bud yakih dvoh reber e1 displaystyle e 1 i e2 displaystyle e 2 v G C displaystyle G setminus C isnuye shlyah u G displaystyle G yakij pochinayetsya v e1 displaystyle e 1 zakinchuyetsya v e2 displaystyle e 2 i ne maye vnutrishnih tochok sho nalezhat C displaystyle C C displaystyle C ye periferijnim ciklom yaksho vin ye porodzhenim ciklom iz vlastivistyu za yakoyi pidgraf G C displaystyle G setminus C utvorenij vidalennyam reber i vershin ciklu C displaystyle C zv yaznij Yaksho C displaystyle C ye bud yakim pidgrafom grafa G displaystyle G mist grafa C displaystyle C ye minimalnim pidgrafom B displaystyle B grafa G displaystyle G yakij ne maye spilnih reber z C displaystyle C i maye vlastivist za yakoyi vsi jogo tochki priyednannya vershini sumizhni rebram yaki nalezhat B displaystyle B i G B displaystyle G setminus B odnochasno nalezhat C displaystyle C Prostij cikl C displaystyle C ye periferijnim yaksho vin maye rivno odin mist Legko bachiti ekvivalentnist cih viznachen zv yaznij pidgraf grafa G C displaystyle G setminus C razom iz rebrami sho zv yazuyut jogo z C displaystyle C abo horda ciklu yaka porushuye porodzhennya ciklu v bud yakomu vipadku maye buti mostom i maye buti takozh klas ekvivalentnosti binarnogo vidnoshennya na rebrah u yakomu dva rebra pov yazani yaksho voni ye kincyami shlyahu bez vnutrishnih vershin u C displaystyle C VlastivostiPeriferijni cikli z yavlyayutsya v teoriyi bagatogrannih grafiv tobto vershinno 3 zv yaznih planarnih grafiv Dlya bud yakogo planarnogo grafa G displaystyle G i bud yakogo planarnogo vkladennya G displaystyle G mezhi vkladennya porodzheni ciklami mayut buti periferijnimi ciklami U bagatogrannomu grafi vsi grani ye periferijnimi ciklami i bud yakij periferijnij cikl ye grannyu Zvidsi viplivaye sho do kombinatornoyi ekvivalentnosti viboru zovnishnoyi grani ta oriyentaciyi ploshini bud yakij bagatogrannij graf maye unikalne planarne vkladennya U planarnih grafah prostir cikliv utvorenij granyami ale v neplanarnih grafah periferijni cikli vidigrayut analogichnu rol dlya bud yakogo vershinno 3 zv yazanogo skinchennogo grafa ciklichnij prostir utvoryuyut periferijni cikli Rezultat mozhna poshiriti na lokalno skinchenni neskinchenni grafi Zokrema zvidsi viplivaye sho 3 zv yazni grafi garantovano mistyat periferijni cikli Isnuyut 2 zv yazni grafi yaki ne mistyat periferijnih cikliv prikladom ye povnij dvochastkovij graf K2 4 displaystyle K 2 4 v yakomu bud yakij cikl maye dva mosti ale yaksho 2 zv yaznij graf maye minimalnij stepin 3 to vin mistit prinajmni odin periferijnij cikl Periferijni cikli v 3 zv yaznih grafah mozhna obchisliti za linijnij chas yih vikoristovuyut dlya rozrobki testiv planarnosti Yih takozh rozshireno do zagalnishogo ponyattya nerozdilyuvalnih vushnih rozkladiv U deyakih algoritmah dlya perevirki planarnosti grafiv korisno znajti cikl yakij ne ye periferijnim z metoyu rozbittya zadachi na menshi pidzadachi U dvozv yaznomu grafi z konturnim rangom menshim vid 3 takomu yak cikl abo teta graf bud yakij cikl ye periferijnim ale bud yakij dvozv yaznij graf z konturnim rangom 3 i bilshe maye neperiferijnij cikl yakij mozhna znajti za linijnij chas Uzagalnyuyuchi hordalni grafi Sejmur i Viver viznachili stisnutij graf yak graf u yakomu bud yakij periferijnij cikl ye trikutnikom Voni opisali ci grafi yak sumi za klikami hordalnih grafiv i maksimalnih planarnih grafiv Pov yazani ponyattyaPeriferijni cikli nazivali takozh nerozdilyuvalnimi ciklami ale cej termin dvoznachnij oskilki vin vikoristovuyetsya she dlya dvoh inshih ponyat dlya prostih cikliv vidalennya yakih robit reshtu grafa nezv yaznoyu i dlya cikliv topologichnogo vkladennya grafa takih sho virizannya vzdovzh ciklu ne robit nezv yaznoyu poverhnyu v yaku graf ukladeno U matroyidah nerozdilyuvalnij cikl ce cikl matroyida tobto minimalna zalezhna mnozhina za yakoyi en ciklu zalishaye menshij matroyid yakij ye zv yaznim tobto yakij ne mozhna rozbiti na pryamu sumu matroyidiv Vin analogichnij periferijnim ciklam ale ne totozhnij navit u en matroyidi v yakih cikli ye prostimi ciklami grafa Napriklad u povnomu dvochastkovomu grafi K2 3 displaystyle K 2 3 bud yakij cikl ye periferijnim vin maye lishe odin mist shlyah iz dvoh reber ale grafovij matroyid utvorenij cim mostom ne zv yaznij tak sho niyakij cikl grafovogo matroyida grafa K2 3 displaystyle K 2 3 ne ye nerozdilyuvalnim PrimitkiTutte 1963 Tutte 1963 s 743 767 Di Battista Eades Tamassia Tollis 1998 s 74 75 Ce viznachennya vikoristav Brun Bruhn 2004 Odnak Brun vidriznyav vipadok sho G displaystyle G maye izolovani vershini vid nezv yaznosti viklikanoyi vidalennyam ciklu C displaystyle C Ne plutati z mostom inshim ponyattyam z takoyu zh nazvoyu Tutte 1960 s 304 320 Ce viznachennya periferijnih cikliv spochatku vikoristav Tatt Tutte 1963 Sejmur i Viver Seymour Weaver 1984 vikoristali take same viznachennya periferijnogo ciklu ale z inshim viznachennyam mosta yake nagaduye viznachennya porodzhenih cikliv dlya periferijnih cikliv Div napriklad teoremu 2 4 u statti Tatta Tutte 1960 yaka pokazuye sho mnozhini vershin mostiv pov yazani shlyahami div stattyu Sejmur i Vivera Seymour Weaver 1984 dlya viznachennya mostiv za dopomogoyu hord i zv yaznih komponent a takozh stattyu Di Battista Idsa Tamassia Tollisa Di Battista Eades Tamassia Tollis 1998 dlya viznachennya mostiv za dopomogoyu klasiv ekvivalentnosti binarnogo vidnoshennya na rebrah Tutte 1963 s Theorems 2 7 i 2 8 Div zauvazhennya pislya teoremi 2 8 u statti Tatta Tutte 1963 Yak zauvazhiv Tatt ce bulo vzhe vidomo Vitni Whitney 1932 Tutte 1963 s Theorem 2 5 Bruhn 2004 s 235 256 Thomassen Toft 1981 s 199 224 Schmidt 2014 s 967 978 Di Battista Eades Tamassia Tollis 1998 s 75 76 Lemma 3 4 Seymour Weaver 1984 Seymour Weaver 1984 s 241 251 Div napriklad Borse Waphare 2008 Div napriklad Cabello Mohar 2007 Maia Lemos Melo 2007 s 162 171 LiteraturaTutte W T How to draw a graph Proceedings of the London Mathematical Society 1963 T 13 S 743 767 Third Series DOI 10 1112 plms s3 13 1 743 Giuseppe Di Battista Peter Eades Roberto Tamassia Ioannis G Tollis Graph Drawing Algorithms for the Visualization of Graphs Prentice Hall 1998 S 74 75 ISBN 978 0 13 301615 4 Tutte W T Convex representations of graphs Proceedings of the London Mathematical Society 1960 T 10 S 304 320 Third Series DOI 10 1112 plms s3 10 1 304 en Non separable and planar graphs Transactions of the American Mathematical Society 1932 T 34 vip 2 S 339 362 DOI 10 2307 1989545 Henning Bruhn The cycle space of a 3 connected locally finite graph is generated by its finite and infinite peripheral circuits Journal of Combinatorial Theory 2004 T 92 vip 2 S 235 256 Series B DOI 10 1016 j jctb 2004 03 005 Carsten Thomassen Bjarne Toft Non separating induced cycles in graphs Journal of Combinatorial Theory 1981 T 31 vip 2 S 199 224 Series B DOI 10 1016 S0095 8956 81 80025 1 Jens M Schmidt The Mondshein Sequence Proceedings of the 41st International Colloquium on Automata Languages and Programming ICALP 14 2014 S 967 978 DOI 10 1007 978 3 662 43948 7 80 Seymour P D Weaver R W A generalization of chordal graphs Journal of Graph Theory 1984 T 8 vip 2 S 241 251 DOI 10 1002 jgt 3190080206 Borse Y M Waphare B N Vertex disjoint non separating cycles in graphs The Journal of the Indian Mathematical Society 2008 T 75 vip 1 4 S 75 92 2009 New Series Sergio Cabello Bojan Mohar Finding shortest non separating and non contractible cycles for topologically embedded graphs 2007 T 37 vip 2 S 213 235 DOI 10 1007 s00454 006 1292 5 Braulio Maia Junior Manoel Lemos Tereza R B Melo Non separating circuits and cocircuits in matroids Combinatorics complexity and chance Oxford Oxford Univ Press 2007 T 34 S 162 171 Oxford Lecture Ser Math Appl DOI 10 1093 acprof oso 9780198571278 003 0010

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