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

Ця стаття містить правописні лексичні граматичні стилістичні або інші мовні помилки які треба виправити Ви можете допомо

Мінор графу

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

В теорії графів неорієнтований граф Н називається мінором графа G, якщо H можна сформувати з G видаленням ребер і вершин або стягуванням ребер.

Теорія мінорів графів почалася з теореми Вагнера, в якій говориться, що граф є планарним, якщо і тільки якщо його мінори не мають (в собі) ні повний граф K5, ні повний двочастковий граф K3,3.. Теорема Робертсона — Сеймура передбачає, що аналогічна характеризація забороненими мінорами існує для кожної властивості графів, що зберігається шляхом видалення вершин і стягування ребер. Для кожного фіксованого графа H можна перевірити, чи є Н мінором вхідного графа G за поліноміальний час. Разом з характеризацією забороненими мінорами це означає, що кожна властивість графа, збережена при діленні та скороченнях, може бути розпізнана за поліноміальний час.

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

Визначення

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

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

Приклад

У наступному прикладі, граф Н — мінор графа G: H. image

G. image

Наступна діаграма ілюструє трансформацію із G в H: спочатку побудуємо підграф G, видаливши пунктирні ребра (і ізольовану вершину), а потім позначимо сіру кромку (об'єднання двох вершин, які вона з'єднує):

image

Основні гіпотези

Нескладно перевірити, що відношення мінора графа утворює частковий порядок для ізоморфних класів неорієнтованих графів: відношення транзитивно (мінор мінору G є мінором самого G), а G і H можуть бути мінорами один одного тільки якщо вони ізоморфні, тому що будь-яка нетривіальна операція над мінором видаляє незначні ребра і вершини. Глибоке дослідження Ніла Робертсона і Пола Сеймура стверджує, що цей частковий порядок насправді є квазівпорядкуванням: якщо дається нескінченний список G1, G2, … кінцевих графів, то завжди існують два індекси i < j такі, що Gi є мінором Gj. Інший еквівалентний спосіб завдання цього є те, що будь-який набір графів може мати лише кінцеве число мінімальних елементів під порядком мінорів. Цей результат довів гіпотезу, раніше відому як гіпотеза Вагнера (за ); Вагнер припускав її задовго раніше, але опублікував тільки в 1970 році.

Об'єднання мінорно-замкнутих графів

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

Алгоритм

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

Див. також

Примітки

  1. Lovász, (2006), p. 77; Wagner, (1937a).
  2. Lovász, (2006), theorem 4, p. 78; Robertson та Seymour, (2004).
  3. Fellows та Langston, (1988).
  4. Diestel, (2005), Chapter 12: Minors, Trees, and WQO; Robertson та Seymour, (2004).

Посилання

  • Alon, Noga; ; (1990), , [en], 3 (4): 801—808, doi:10.2307/1990903, JSTOR 1990903, MR 1065053, архів оригіналу за 14 лютого 2019, процитовано 27 березня 2016.
  • ; Catlin, P. A.; Erdős, Paul (1980), (PDF), , 1: 195—199, doi:10.1016/s0195-6698(80)80001-1, архів оригіналу (PDF) за 18 березня 2009, процитовано 27 березня 2016.
  • Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2004), , Algorithmica, 40 (3): 211—215, doi:10.1007/s00453-004-1106-1, архів оригіналу за 20 вересня 2019, процитовано 27 березня 2016.
  • Diestel, Reinhard (2005), (вид. 3rd), Berlin, New York: Springer-Verlag, ISBN , архів оригіналу за 28 липня 2011, процитовано 27 березня 2016.
  • Ding, Guoli (1996), Excluding a long double path minor, [en], Series B, 66 (1): 11—23, doi:10.1006/jctb.1996.0002, MR 1368512.
  • Eppstein, David (2000), Diameter and treewidth in minor-closed graph families, Algorithmica, 27: 275—291, arXiv:math.CO/9907126, doi:10.1007/s004530010020, MR 2001c:05132 {{}}: Перевірте значення |mr= ().
  • ; (1988), Nonconstructive tools for proving polynomial-time decidability, , 35 (3): 727—739, doi:10.1145/44483.44491.
  • Grohe, Martin (2003), , , 23 (4): 613—632, doi:10.1007/s00493-003-0037-9, архів оригіналу за 24 лютого 2018, процитовано 27 березня 2016.
  • (1943), Über eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. Ges. Zürich, 88: 133—143.
  • Hall, Dick Wick (1943), A note on primitive skew curves, Bulletin of the American Mathematical Society, 49 (12): 935—936, doi:10.1090/S0002-9904-1943-08065-2.
  • Kostochka, Alexandr V. (1982), The minimum Hadwiger number for graphs with a given mean degree of vertices, Metody Diskret. Analiz. (Russian) , 38: 37—58.
  • Lovász, László (2006), Graph minor theory, Bulletin of the American Mathematical Society, 43 (1): 75—86, doi:10.1090/S0273-0979-05-01088-8.
  • Mader, Wolfgang (1967), Homomorphieeigenschaften und mittlere Kantendichte von Graphen, Mathematische Annalen, 174 (4): 265—268, doi:10.1007/BF01364272.
  • ; (2012), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, т. 28, Springer, с. 62—65, doi:10.1007/978-3-642-27875-4, ISBN , MR 2920058.
  • (2002), (PDF), Notices of the American Mathematical Society, 49 (9): 1084—1086, doi:10.1109/TED.2002.1003756, архів оригіналу (PDF) за 2 квітня 2019, процитовано 27 березня 2016.
  • Plotkin, Serge; Rao, Satish; Smith, Warren D. (1994), Shallow excluded minors and improved graph decompositions, Proc. 5th ACM–SIAM Symp. on Discrete Algorithms (SODA 1994), с. 462—470.
  • ; Wood, David R. (2009), A linear-time algorithm to find a separator in a graph excluding a minor, ACM Transactions on Algorithms, 5 (4): Article 39, doi:10.1145/1597036.1597043.
  • ; (1995), Graph Minors. XIII. The disjoint paths problem, , 63 (1): 39—675, doi:10.1006/jctb.1995.1006.
  • (1999), Recent excluded minor theorems for graphs, (PDF), London Math. Soc. Lecture Note Ser., т. 267, Cambridge: Cambridge Univ. Press, с. 201—222, MR 1725004, архів оригіналу (PDF) за 3 серпня 2016, процитовано 27 березня 2016.
  • Thomason, Andrew (1984), An extremal function for contractions of graphs, , 95 (2): 261—265, doi:10.1017/S0305004100061521.
  • (1937a), Über eine Eigenschaft der ebenen Komplexe, Math. Ann., 114: 570—590, doi:10.1007/BF01594196.

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

Cya stattya mistit pravopisni leksichni gramatichni stilistichni abo inshi movni pomilki yaki treba vipraviti Vi mozhete dopomogti vdoskonaliti cyu stattyu pogodivshi yiyi iz chinnimi movnimi standartami V teoriyi grafiv neoriyentovanij graf N nazivayetsya minorom grafa G yaksho H mozhna sformuvati z G vidalennyam reber i vershin abo styaguvannyam reber Teoriya minoriv grafiv pochalasya z teoremi Vagnera v yakij govoritsya sho graf ye planarnim yaksho i tilki yaksho jogo minori ne mayut v sobi ni povnij graf K5 ni povnij dvochastkovij graf K3 3 Teorema Robertsona Sejmura peredbachaye sho analogichna harakterizaciya zaboronenimi minorami isnuye dlya kozhnoyi vlastivosti grafiv sho zberigayetsya shlyahom vidalennya vershin i styaguvannya reber Dlya kozhnogo fiksovanogo grafa H mozhna pereviriti chi ye N minorom vhidnogo grafa G za polinomialnij chas Razom z harakterizaciyeyu zaboronenimi minorami ce oznachaye sho kozhna vlastivist grafa zberezhena pri dilenni ta skorochennyah mozhe buti rozpiznana za polinomialnij chas Inshi rezultati i domisli za uchastyu minora grafa vklyuchayut teoremu strukturi grafa vidpovidno do yakoyi grafi v yakih nemaye N yak minoru mozhut buti utvoreni shlyahom skleyuvannya bilsh prostih chastin A gipoteza Hadvigera opisuye nemozhlivist pofarbuvati grafi zgidno z isnuyuchim velikogo povnogo grafa yak i jogo minor Vazhlivi varianti minoriv grafa vklyuchayut topologichni minori j zanureni minori ViznachennyaOperaciya styaguvannya rebra vidalyaye rebro z grafa pri odnochasnomu ob yednanni dvoh vershin yaki vono z yednuvalo Neoriyentovanij graf H ye minorom inshogo neoriyentovanogo grafa G yaksho graf shozhij do H mozhe buti otrimanij z G styaguvannyam deyakih reber vidalennyam deyakih reber i vidalennyam deyakih izolovanih vershin Poryadok v yakomu poslidovnist takih skorochen i viluchen vikonuyetsya z G ne vplivaye na otrimanij graf H Minori grafiv chasto vivchayutsya v bilsh zagalnomu konteksti matroyidnih minoriv U zv yazku z cim zavedeno vvazhati sho vsi grafi ye bilshe multigrafom nizh prostim grafom Cya tochka zoru maye perevagu v tomu sho krajovi vidalennya zalishayut rang grafa bez zmin a krajovi sutichki zavzhdi zmenshuyut rang na odinicyu PrikladU nastupnomu prikladi graf N minor grafa G H G Nastupna diagrama ilyustruye transformaciyu iz G v H spochatku pobuduyemo pidgraf G vidalivshi punktirni rebra i izolovanu vershinu a potim poznachimo siru kromku ob yednannya dvoh vershin yaki vona z yednuye Osnovni gipoteziNeskladno pereviriti sho vidnoshennya minora grafa utvoryuye chastkovij poryadok dlya izomorfnih klasiv neoriyentovanih grafiv vidnoshennya tranzitivno minor minoru G ye minorom samogo G a G i H mozhut buti minorami odin odnogo tilki yaksho voni izomorfni tomu sho bud yaka netrivialna operaciya nad minorom vidalyaye neznachni rebra i vershini Gliboke doslidzhennya Nila Robertsona i Pola Sejmura stverdzhuye sho cej chastkovij poryadok naspravdi ye kvazivporyadkuvannyam yaksho dayetsya neskinchennij spisok G1 G2 kincevih grafiv to zavzhdi isnuyut dva indeksi i lt j taki sho Gi ye minorom Gj Inshij ekvivalentnij sposib zavdannya cogo ye te sho bud yakij nabir grafiv mozhe mati lishe kinceve chislo minimalnih elementiv pid poryadkom minoriv Cej rezultat doviv gipotezu ranishe vidomu yak gipoteza Vagnera za Vagner pripuskav yiyi zadovgo ranishe ale opublikuvav tilki v 1970 roci Ob yednannya minorno zamknutih grafivBagato ob yednan grafiv mayut taku vlastivist sho kozhen minor grafa z F takozh znahoditsya v F takij klas nazivayetsya minorno zamknutim Napriklad v bud yakomu planarnomu grafi abo bud yakomu vkladenomu grafi na fiksovanij topologichnoyi poverhni ni vidalennya reber ni styaguvannya reber ne mozhut zbilshiti rid vkladenogo grafa Takim chinom planarni grafi i yih vkladeni grafi na bud yakij zakriplenij poverhni formuyut minorno zamknuti ob yednannya AlgoritmYaksho N ye ciklichnim grafom z takoyu zh kilkistyu vershin yak i G to N minor G todi i tilki todi koli G mistit gamiltoniv cikl Prote koli G ye chastinoyu vhidnogo ale N fiksovanij ce mozhe buti virisheno za polinomialnij chas Shlyahom zastosuvannya algoritmu polinomialnogo chasu dlya perevirki na te chi mistit danij graf bud yakij z vkazanih minoriv mozhna rozpiznati chleni bud yakogo minorno zamknutogo ob yednannya za polinomialnij chas Odnak dlya togo shob konstruktivno zastosuvati cej rezultat neobhidno znati zaboroneni minori simejstva grafiv Div takozhMinor obmezhenoyi glibiniPrimitkiLovasz 2006 p 77 Wagner 1937a Lovasz 2006 theorem 4 p 78 Robertson ta Seymour 2004 Fellows ta Langston 1988 Diestel 2005 Chapter 12 Minors Trees and WQO Robertson ta Seymour 2004 PosilannyaAlon Noga 1990 en 3 4 801 808 doi 10 2307 1990903 JSTOR 1990903 MR 1065053 arhiv originalu za 14 lyutogo 2019 procitovano 27 bereznya 2016 Catlin P A Erdos Paul 1980 PDF 1 195 199 doi 10 1016 s0195 6698 80 80001 1 arhiv originalu PDF za 18 bereznya 2009 procitovano 27 bereznya 2016 Demaine Erik D Hajiaghayi MohammadTaghi 2004 Algorithmica 40 3 211 215 doi 10 1007 s00453 004 1106 1 arhiv originalu za 20 veresnya 2019 procitovano 27 bereznya 2016 Diestel Reinhard 2005 vid 3rd Berlin New York Springer Verlag ISBN 978 3 540 26183 4 arhiv originalu za 28 lipnya 2011 procitovano 27 bereznya 2016 Ding Guoli 1996 Excluding a long double path minor en Series B 66 1 11 23 doi 10 1006 jctb 1996 0002 MR 1368512 Eppstein David 2000 Diameter and treewidth in minor closed graph families Algorithmica 27 275 291 arXiv math CO 9907126 doi 10 1007 s004530010020 MR 2001c 05132 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Citation title Shablon Citation citation a Perevirte znachennya mr dovidka 1988 Nonconstructive tools for proving polynomial time decidability 35 3 727 739 doi 10 1145 44483 44491 Grohe Martin 2003 23 4 613 632 doi 10 1007 s00493 003 0037 9 arhiv originalu za 24 lyutogo 2018 procitovano 27 bereznya 2016 1943 Uber eine Klassifikation der Streckenkomplexe Vierteljschr Naturforsch Ges Zurich 88 133 143 Hall Dick Wick 1943 A note on primitive skew curves Bulletin of the American Mathematical Society 49 12 935 936 doi 10 1090 S0002 9904 1943 08065 2 Kostochka Alexandr V 1982 The minimum Hadwiger number for graphs with a given mean degree of vertices Metody Diskret Analiz Russian 38 37 58 Lovasz Laszlo 2006 Graph minor theory Bulletin of the American Mathematical Society 43 1 75 86 doi 10 1090 S0273 0979 05 01088 8 Mader Wolfgang 1967 Homomorphieeigenschaften und mittlere Kantendichte von Graphen Mathematische Annalen 174 4 265 268 doi 10 1007 BF01364272 2012 Sparsity Graphs Structures and Algorithms Algorithms and Combinatorics t 28 Springer s 62 65 doi 10 1007 978 3 642 27875 4 ISBN 978 3 642 27874 7 MR 2920058 2002 PDF Notices of the American Mathematical Society 49 9 1084 1086 doi 10 1109 TED 2002 1003756 arhiv originalu PDF za 2 kvitnya 2019 procitovano 27 bereznya 2016 Plotkin Serge Rao Satish Smith Warren D 1994 Shallow excluded minors and improved graph decompositions Proc 5th ACM SIAM Symp on Discrete Algorithms SODA 1994 s 462 470 Wood David R 2009 A linear time algorithm to find a separator in a graph excluding a minor ACM Transactions on Algorithms 5 4 Article 39 doi 10 1145 1597036 1597043 1995 Graph Minors XIII The disjoint paths problem 63 1 39 675 doi 10 1006 jctb 1995 1006 1999 Recent excluded minor theorems for graphs PDF London Math Soc Lecture Note Ser t 267 Cambridge Cambridge Univ Press s 201 222 MR 1725004 arhiv originalu PDF za 3 serpnya 2016 procitovano 27 bereznya 2016 Thomason Andrew 1984 An extremal function for contractions of graphs 95 2 261 265 doi 10 1017 S0305004100061521 1937a Uber eine Eigenschaft der ebenen Komplexe Math Ann 114 570 590 doi 10 1007 BF01594196

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