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

У візуалізації графів і en число нахилів графа це найменша можлива кількість різних кутових коефіцієнтів ребер у малюнку

Число нахилів графа

Число нахилів графа

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

image
Малюнок графа Петерсена з числом нахилів 3

Повні графи

Хоча близькі задачі комбінаторної геометрії вивчали й раніше (Скотт у 1970 і Джемісон у 1984), задачу визначення числа нахилів графа поставили Вейд і Чу, показавши, що число нахилів графа з image вершинами повного графа image дорівнює рівно image. Малюнок графа з таким числом нахилів можна отримати, розташувавши вершини графа в кутах правильного многокутника.

Зв'язок зі степенем графа

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

Існують графи з найбільшим степенем 5, що мають довільно велике число нахилів. Однак будь-який граф із найбільшим степенем 3 має не більше чотирьох нахилів. Результат Вейда і Чу (Wade, Chu, (1994)) для повного графа image показує, що ця межа точна. Не будь-який набір із чотирьох нахилів підходить для малювання всіх графів степеня 3 — набір нахилів підходить для малювання тоді й лише тоді, коли вони є нахилами сторін та діагоналей паралелограма. Зокрема, будь-який граф степеня 3 можна намалювати так, що його ребра або паралельні осям, або паралельні основним діагоналям цілочисельної ґратки. Невідомо, чи обмежене число нахилів графів з найбільшим степенем 4.

image
Метод Кезега, Паха та Палвелді комбінування пакування кіл і дерева квадрантів для отримання обмеженого числа нахилів для планарних графів з обмеженим степенем

Планарні графи

Як показали Кезег, Пах і Палвелді (Keszegh, Pach, Pálvölgyi, (2011)), будь-який планарний граф має плоский малюнок у вигляді прямих відрізків, у якому число різних нахилів є функцією від степеня графа. Їхнє доведення ґрунтується на побудові Малиця і Папакостаса (Malitz, Papakostas, (1994)) для обмеження кутової роздільності планарних графів як функції степеня. Степінь обмежують доповненням графа до максимального планарного графа без збільшення його степеня більш ніж на сталий множник, а потім застосовують для подання цього розширеного графа як набору кіл, що дотикаються між собою. Якщо степінь початкового графа обмежено, відношення радіусів суміжних кіл у пакуванні буде також обмеженим, звідки, у свою чергу, випливає, що застосування дерева квадрантів для всіх вершин графа в точці всередині кола дає нахили, які є відношеннями малих цілих чисел. Число різних нахилів, що отримується при цій побудові, є експонентою від степеня графа.

Складність

Визначення, чи дорівнює число нахилів 2, є NP-повною задачею. Звідси випливає, що NP-складною задачею є визначення числа нахилів довільного графа або апроксимація цього числа з гарантованою ефективністю, кращою за 3/2.

Перевірка, чи можна зобратити планарний граф планарним малюнком із числом нахилів 2, також є NP-повною задачею.

Примітки

  1. Wade, Chu, 1994.
  2. Довели незалежно Барат, Матоушек, Вуд (Barát, Matoušek, Wood, (2006)) і Пах, Палвелді (Pach, Pálvölgyi, (2006)), коли розв'язували задачу, яку поставив Дуймович, Судерман і Шарір (Dujmović, Suderman, Wood, (2005)). Див. теореми 5.1 і 5.2 у Паха і Шаріра (Pach, Sharir, (2009)).
  3. Муккамала, Сегеді (Mukkamala, Szegedy, (2009)), які покращили раніший результат Кезега, Палвелді, Тота (Keszegh, Pach, Pálvölgyi, Tóth, (2008)). Див. теорему 5.3 у Паха і Шаріра (Pach, Sharir, (2009)).
  4. Mukkamala, Pálvölgyi, 2012.
  5. Pach, Sharir, 2009.
  6. Keszegh, Pach, Pálvölgyi, 2011.
  7. Hansen, 1988.
  8. Formann, Hagerup, Haralambides, Kaufmann, 1993.
  9. Eades, Hong, Poon, 2010.
  10. Maňuch, Patterson, Poon, Thachuk, 2011.
  11. Garg, Tamassia, 2001.

Література

  • János Barát, Jiří Matoušek, David R. Wood. Bounded-degree graphs have arbitrarily large geometric thickness // . — 2006. — Т. 13, вип. 1. — С. R3.
  • Vida Dujmović, Matthew Suderman, David R. Wood. Graph Drawing: 12th International Symposium, GD 2004, New York, NY, USA, September 29-October 2, 2004, Revised Selected Papers / János Pach. — Berlin : Springer-Verlag, 2005. — Т. 3383. — С. 122–132. — () — DOI:10.1007/978-3-540-31843-9_14.
  • Peter Eades, Seok-Hee Hong, Sheung-Hung Poon. Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers / David Eppstein, Emden R. Gansner. — Berlin : Springer, 2010. — Т. 5849. — С. 232–243. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-11805-0_23.
  • M. Formann, T. Hagerup, J. Haralambides, M. Kaufmann, F. T. Leighton, A. Symvonis, E. Welzl, G. J. Woeginger. Drawing graphs in the plane with high resolution // . — 1993. — Т. 22, вип. 5. — С. 1035–1052. — DOI:10.1137/0222063.
  • Ashim Garg, Roberto Tamassia. On the computational complexity of upward and rectilinear planarity testing // . — 2001. — Т. 31, вип. 2. — С. 601–625. — DOI:10.1137/S0097539794277123.
  • Lowell J. Hansen. On the Rodin and Sullivan ring lemma // Complex Variables, Theory and Application. — 1988. — Т. 10, вип. 1. — С. 23–30. — DOI:10.1080/17476938808814284.
  • Robert E. Jamison. Planar configurations which determine few slopes // . — 1984. — Т. 16, вип. 1. — С. 17–34. — DOI:10.1007/BF00147419.
  • Balázs Keszegh, János Pach, Dömötör Pálvölgyi. Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers / Ulrik Brandes, Sabine Cornelsen. — Heidelberg : Springer, 2011. — Т. 6502. — С. 293–304. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-18469-7_27.
  • Balázs Keszegh, János Pach, Dömötör Pálvölgyi, Géza Tóth. Drawing cubic graphs with at most five slopes // . — 2008. — Т. 40, вип. 2. — С. 138–147. — DOI:10.1016/j.comgeo.2007.05.003.
  • Seth Malitz, Achilleas Papakostas. On the angular resolution of planar graphs // SIAM Journal on Discrete Mathematics. — 1994. — Т. 7, вип. 2. — С. 172–183. — DOI:10.1137/S0895480193242931.
  • Ján Maňuch, Murray Patterson, Sheung-Hung Poon, Chris Thachuk. Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers / Ulrik Brandes, Sabine Cornelsen. — Heidelberg : Springer, 2011. — Т. 6502. — С. 305–316. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-18469-7_28.
  • Padmini Mukkamala, Mario Szegedy. Geometric representation of cubic graphs with four directions // . — 2009. — Т. 42, вип. 9. — С. 842–851. — DOI:10.1016/j.comgeo.2009.01.005.
  • Padmini Mukkamala, Dömötör Pálvölgyi. Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21-23, 2011, Revised Selected Papers / Marc van Kreveld, Bettina Speckmann. — Springer, 2012. — Т. 7034. — С. 254–265. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-25878-7_25.
  • János Pach, Dömötör Pálvölgyi. Bounded-degree graphs can have arbitrarily large slope numbers // . — 2006. — Т. 13, вип. 1. — С. N1.
  • János Pach, Micha Sharir. Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures. — American Mathematical Society, 2009. — Т. 152. — С. 126–127. — (Mathematical Surveys and Monographs)
  • P. R. Scott. On the sets of directions determined by n points // American Mathematical Monthly. — 1970. — Т. 77. — С. 502–505. — DOI:10.2307/2317384.
  • G. A. Wade, J.-H. Chu. Drawability of complete graphs using a minimal slope set // . — 1994. — Т. 37, вип. 2. — С. 139–142. — DOI:10.1093/comjnl/37.2.139.

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

U vizualizaciyi grafiv i en chislo nahiliv grafa ce najmensha mozhliva kilkist riznih kutovih koeficiyentiv reber u malyunku grafa na yakomu vershini podano tochkami evklidovoyi ploshini a rebrami ye vidrizki yaki ne prohodyat cherez vershini neincidentni cim rebram Malyunok grafa Petersena z chislom nahiliv 3Povni grafiHocha blizki zadachi kombinatornoyi geometriyi vivchali j ranishe Skott u 1970 i Dzhemison u 1984 zadachu viznachennya chisla nahiliv grafa postavili Vejd i Chu pokazavshi sho chislo nahiliv grafa z n displaystyle n vershinami povnogo grafa K n displaystyle K n dorivnyuye rivno n displaystyle n Malyunok grafa z takim chislom nahiliv mozhna otrimati roztashuvavshi vershini grafa v kutah pravilnogo mnogokutnika Zv yazok zi stepenem grafaZrozumilo sho chislo nahiliv grafa z najbilshim stepenem d displaystyle d ne menshe d 2 displaystyle lceil d 2 rceil oskilki maksimum dva incidentni rebra vershini stepenya d mozhut lezhati na odnij pryamij mati odin nahil Tochnishe chislo nahiliv ne menshe linijnoyi derevnosti grafa oskilki rebra odnogo nahilu mayut utvoryuvati linijnij lis a linijna derevnist u svoyu chergu ne mensha nizh d 2 displaystyle lceil d 2 rceil Isnuyut grafi z najbilshim stepenem 5 sho mayut dovilno velike chislo nahiliv Odnak bud yakij graf iz najbilshim stepenem 3 maye ne bilshe chotiroh nahiliv Rezultat Vejda i Chu Wade Chu 1994 dlya povnogo grafa K 4 displaystyle K 4 pokazuye sho cya mezha tochna Ne bud yakij nabir iz chotiroh nahiliv pidhodit dlya malyuvannya vsih grafiv stepenya 3 nabir nahiliv pidhodit dlya malyuvannya todi j lishe todi koli voni ye nahilami storin ta diagonalej paralelograma Zokrema bud yakij graf stepenya 3 mozhna namalyuvati tak sho jogo rebra abo paralelni osyam abo paralelni osnovnim diagonalyam cilochiselnoyi gratki Nevidomo chi obmezhene chislo nahiliv grafiv z najbilshim stepenem 4 Metod Kezega Paha ta Palveldi kombinuvannya pakuvannya kil i dereva kvadrantiv dlya otrimannya obmezhenogo chisla nahiliv dlya planarnih grafiv z obmezhenim stepenemPlanarni grafiYak pokazali Kezeg Pah i Palveldi Keszegh Pach Palvolgyi 2011 bud yakij planarnij graf maye ploskij malyunok u viglyadi pryamih vidrizkiv u yakomu chislo riznih nahiliv ye funkciyeyu vid stepenya grafa Yihnye dovedennya gruntuyetsya na pobudovi Malicya i Papakostasa Malitz Papakostas 1994 dlya obmezhennya kutovoyi rozdilnosti planarnih grafiv yak funkciyi stepenya Stepin obmezhuyut dopovnennyam grafa do maksimalnogo planarnogo grafa bez zbilshennya jogo stepenya bilsh nizh na stalij mnozhnik a potim zastosovuyut dlya podannya cogo rozshirenogo grafa yak naboru kil sho dotikayutsya mizh soboyu Yaksho stepin pochatkovogo grafa obmezheno vidnoshennya radiusiv sumizhnih kil u pakuvanni bude takozh obmezhenim zvidki u svoyu chergu viplivaye sho zastosuvannya dereva kvadrantiv dlya vsih vershin grafa v tochci vseredini kola daye nahili yaki ye vidnoshennyami malih cilih chisel Chislo riznih nahiliv sho otrimuyetsya pri cij pobudovi ye eksponentoyu vid stepenya grafa SkladnistViznachennya chi dorivnyuye chislo nahiliv 2 ye NP povnoyu zadacheyu Zvidsi viplivaye sho NP skladnoyu zadacheyu ye viznachennya chisla nahiliv dovilnogo grafa abo aproksimaciya cogo chisla z garantovanoyu efektivnistyu krashoyu za 3 2 Perevirka chi mozhna zobratiti planarnij graf planarnim malyunkom iz chislom nahiliv 2 takozh ye NP povnoyu zadacheyu PrimitkiWade Chu 1994 Doveli nezalezhno Barat Matoushek Vud Barat Matousek Wood 2006 i Pah Palveldi Pach Palvolgyi 2006 koli rozv yazuvali zadachu yaku postaviv Dujmovich Suderman i Sharir Dujmovic Suderman Wood 2005 Div teoremi 5 1 i 5 2 u Paha i Sharira Pach Sharir 2009 Mukkamala Segedi Mukkamala Szegedy 2009 yaki pokrashili ranishij rezultat Kezega Palveldi Tota Keszegh Pach Palvolgyi Toth 2008 Div teoremu 5 3 u Paha i Sharira Pach Sharir 2009 Mukkamala Palvolgyi 2012 Pach Sharir 2009 Keszegh Pach Palvolgyi 2011 Hansen 1988 Formann Hagerup Haralambides Kaufmann 1993 Eades Hong Poon 2010 Manuch Patterson Poon Thachuk 2011 Garg Tamassia 2001 LiteraturaJanos Barat Jiri Matousek David R Wood Bounded degree graphs have arbitrarily large geometric thickness 2006 T 13 vip 1 S R3 Vida Dujmovic Matthew Suderman David R Wood Graph Drawing 12th International Symposium GD 2004 New York NY USA September 29 October 2 2004 Revised Selected Papers Janos Pach Berlin Springer Verlag 2005 T 3383 S 122 132 DOI 10 1007 978 3 540 31843 9 14 Peter Eades Seok Hee Hong Sheung Hung Poon Graph Drawing 17th International Symposium GD 2009 Chicago IL USA September 22 25 2009 Revised Papers David Eppstein Emden R Gansner Berlin Springer 2010 T 5849 S 232 243 Lecture Notes in Computer Science DOI 10 1007 978 3 642 11805 0 23 M Formann T Hagerup J Haralambides M Kaufmann F T Leighton A Symvonis E Welzl G J Woeginger Drawing graphs in the plane with high resolution 1993 T 22 vip 5 S 1035 1052 DOI 10 1137 0222063 Ashim Garg Roberto Tamassia On the computational complexity of upward and rectilinear planarity testing 2001 T 31 vip 2 S 601 625 DOI 10 1137 S0097539794277123 Lowell J Hansen On the Rodin and Sullivan ring lemma Complex Variables Theory and Application 1988 T 10 vip 1 S 23 30 DOI 10 1080 17476938808814284 Robert E Jamison Planar configurations which determine few slopes 1984 T 16 vip 1 S 17 34 DOI 10 1007 BF00147419 Balazs Keszegh Janos Pach Domotor Palvolgyi Graph Drawing 18th International Symposium GD 2010 Konstanz Germany September 21 24 2010 Revised Selected Papers Ulrik Brandes Sabine Cornelsen Heidelberg Springer 2011 T 6502 S 293 304 Lecture Notes in Computer Science DOI 10 1007 978 3 642 18469 7 27 Balazs Keszegh Janos Pach Domotor Palvolgyi Geza Toth Drawing cubic graphs with at most five slopes 2008 T 40 vip 2 S 138 147 DOI 10 1016 j comgeo 2007 05 003 Seth Malitz Achilleas Papakostas On the angular resolution of planar graphs SIAM Journal on Discrete Mathematics 1994 T 7 vip 2 S 172 183 DOI 10 1137 S0895480193242931 Jan Manuch Murray Patterson Sheung Hung Poon Chris Thachuk Graph Drawing 18th International Symposium GD 2010 Konstanz Germany September 21 24 2010 Revised Selected Papers Ulrik Brandes Sabine Cornelsen Heidelberg Springer 2011 T 6502 S 305 316 Lecture Notes in Computer Science DOI 10 1007 978 3 642 18469 7 28 Padmini Mukkamala Mario Szegedy Geometric representation of cubic graphs with four directions 2009 T 42 vip 9 S 842 851 DOI 10 1016 j comgeo 2009 01 005 Padmini Mukkamala Domotor Palvolgyi Graph Drawing 19th International Symposium GD 2011 Eindhoven The Netherlands September 21 23 2011 Revised Selected Papers Marc van Kreveld Bettina Speckmann Springer 2012 T 7034 S 254 265 Lecture Notes in Computer Science DOI 10 1007 978 3 642 25878 7 25 Janos Pach Domotor Palvolgyi Bounded degree graphs can have arbitrarily large slope numbers 2006 T 13 vip 1 S N1 Janos Pach Micha Sharir Combinatorial Geometry and Its Algorithmic Applications The Alcala Lectures American Mathematical Society 2009 T 152 S 126 127 Mathematical Surveys and Monographs P R Scott On the sets of directions determined by n points American Mathematical Monthly 1970 T 77 S 502 505 DOI 10 2307 2317384 G A Wade J H Chu Drawability of complete graphs using a minimal slope set 1994 T 37 vip 2 S 139 142 DOI 10 1093 comjnl 37 2 139

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