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

У теорії графів графом k степені Gk неорієнтованого графа G є інший граф що має таку ж саму кількість вершин але дві йог

Степінь графа

Степінь графа

У теорії графів, графом k-степені Gk неорієнтованого графа G є інший граф, що має таку ж саму кількість вершин, але дві його вершини є суміжними, коли відстань між ними не перевищує k. Аналогічну термінологію використовують при піднесенні чисел до степеня: G2 називається G квадрат, G3 називається G куб, тощо.

image
Квадрат графа

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

Властивості

Якщо граф має діаметр d, то його граф d-степені — повний граф.

Розфарбовування

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

Хроматичне число та виродження планарного графа степені k максимального ступеня Δ дорівнює image, де оцінка виродження відображає, що для розфарбування графа такою великою кількістю кольорів може бути використаний алгоритм жадібної розмальовки. Для окремого випадку квадрата планарного графа у 1977 році Вегнер висловив припущення, що хроматичне число квадрату планарного графа не перевищує image, так само відомо, що хроматичне число не перевищує image. Взагалі, для будь-якого графа з виродженням d та максимальним степенем Δ, виродження квадрату графа дорівнює O(dΔ), тож для багатьох з щільних графів, окрім планарних, так само хроматичне число квадрату пропорційне Δ.

Незважаючи на те, що хроматичне число квадрату непланарного графа може бути пропорційним (у найгіршому випадку) Δ, воно буде меншим для графів з великим обхватом, обмежених у цьому випадку O(Δ2/log Δ).

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

Гамільтоновість

Куб кожного зв'язного графа обов'язково містить Гамільтонів цикл. Але квадрат зв'язного графа не обов'язково є гамільтоновим, і це є NP-повною задачею — виявити, чи є квадрат гамільтоновим. Проте, за теоремою Фляйшнера, квадрат 2-вершинно-зв'язного графа завжди є гамільтоновим.

Складність обчислення

Граф степені k, що має n вершин і m ребер може бути обчислений за О(mn) часу, за допомогою виконання пошуку в ширину, починаючи з кожної вершини для визначення відстані до всіх інших вершин. Як альтернатива, якщо А — матриця суміжності для графа, у якому змінені усі нульові елементи на головній діагоналі (на ненулеві), то ненулеві елементи матриці Ак дають матрицю суміжності графа степеня k, з цього випливає, що побудова степені k може бути здійснена за той час, що знаходиться у межах логарифмічного фактору часу для множення матриць.

Поняття степені листа тісно пов'язано з k-степенем дерева, індуковане листям дерева G. Цей клас графів знайшов застосування у філогенезі.

Було досягнуто першого твердого результату: Маючи граф, вирішити, чи є квадрат іншого графа NP-повною задачею. Крім того, NP-повною задачею є визначити, чи є граф степенем іншого графа коли k ≥ 2 , чи є він k-степенем двочастинного графа при k>2.

Примітки

  1. Bondy, Andrian; Murty, U.S.R. (2008). Graph Theory (English) . Springer: Graduate Texts in Mathematics 244. с. 82. ISBN .
  2. Weisstein, Eric W. Graph Power. MathWorld.
  3. Agnarsson, Geir; Magnús, M. (2000). "Coloring powers of planar graphs". San Francisco, California: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00). с. 654—662.
  4. Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, F.; Symvonis, A.; Welzl, E.; Woeginger, G. (1 жовтня 1993). Drawing Graphs in the Plane with High Resolution. SIAM Journal on Computing. Т. 22, № 5. с. 1035—1052. doi:10.1137/0222063. ISSN 0097-5397. Процитовано 30 березня 2016.
  5. Kramer, Florica; Kramer, Horst (6 лютого 2008). A survey on the distance-colouring of graphs. Discrete Mathematics. Т. 308, № 2–3. с. 422—426. doi:10.1016/j.disc.2006.11.059. Процитовано 30 березня 2016.
  6. Molloy, Michael; Salavatipour, Mohammad R. (1 липня 2005). A bound on the chromatic number of the square of a planar graph. Journal of Combinatorial Theory, Series B. Т. 94, № 2. с. 189—213. doi:10.1016/j.jctb.2004.12.005. Процитовано 30 березня 2016.
  7. Alon, Noga; Mohar, Bojan (1 січня 2002). The Chromatic Number of Graph Powers. Combinatorics, Probability and Computing. Т. 11, № 01. с. 1—10. doi:10.1017/S0963548301004965. ISSN 1469-2163. Процитовано 30 березня 2016.
  8. Agnarsson та Halldórsson, (2000) list publications proving NP-hardness for general graphs by McCormick (1983) and Lin and Skiena (1995), and for planar graphs by Ramanathan and Lloyd (1992, 1993).
  9. Bondy та Murty, (2008), p. 105.
  10. Underground, Paris (1978), On graphs with Hamiltonian squares, , 21 (3): 323, doi:10.1016/0012-365X(78)90164-4, MR 0522906.
  11. Diestel, Reinhard (2012), 10. Hamiltonian cycles, Graph Theory (PDF) (вид. corrected 4th electronic).
  12. Nishimura, Naomi; Ragde, Prabhakar; Thilikos, Dimitrios M. (2002), On graph powers for leaf-labeled trees, Journal of Algorithms, 42 (1): 69—108, doi:10.1006/jagm.2001.1195, MR 1874637.
  13. Motwani, R.; Sudan, M. (1994), Computing roots of graphs is hard, Discrete Applied Mathematics, 54: 81—88, doi:10.1016/0166-218x(94)00023-9.
  14. Le, Van Bang; Nguyen, Ngoc Tuy (2010), Hardness results and efficient algorithms for graph powers, Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009, Revised Papers, Lecture Notes in Computer Science, т. 5911, Berlin: Springer, с. 238—249, doi:10.1007/978-3-642-11409-0_21, ISBN , MR 2587715

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

U teoriyi grafiv grafom k stepeni Gk neoriyentovanogo grafa G ye inshij graf sho maye taku zh samu kilkist vershin ale dvi jogo vershini ye sumizhnimi koli vidstan mizh nimi ne perevishuye k Analogichnu terminologiyu vikoristovuyut pri pidnesenni chisel do stepenya G2 nazivayetsya G kvadrat G3 nazivayetsya G kub tosho Kvadrat grafa Stepin grafa slid vidriznyati vid dobutku grafa na sebe yakij na vidminu vid grafa v stepeni maye nabagato bilshe vershin nizh pochatkovij graf VlastivostiYaksho graf maye diametr d to jogo graf d stepeni povnij graf Rozfarbovuvannya Rozfarbovuvannya kvadratu grafa mozhe buti vikoristano dlya rozpodilennya uchasnikiv bezdrotovoyi merezhi zv yazku takim chinom shob niyaki dva uchasniki ne zavazhali odin odnomu chi spilnim susidam ta dlya togo shob viyaviti vizualizaciyu grafa z najbilshoyu kutovoyu rozdilnistyu Hromatichne chislo ta virodzhennya planarnogo grafa stepeni k maksimalnogo stupenya D dorivnyuye O D k 2 displaystyle O Delta lfloor k 2 rfloor de ocinka virodzhennya vidobrazhaye sho dlya rozfarbuvannya grafa takoyu velikoyu kilkistyu koloriv mozhe buti vikoristanij algoritm zhadibnoyi rozmalovki Dlya okremogo vipadku kvadrata planarnogo grafa u 1977 roci Vegner visloviv pripushennya sho hromatichne chislo kvadratu planarnogo grafa ne perevishuye max d 5 3 d 2 1 displaystyle max left d 5 frac 3d 2 1 right tak samo vidomo sho hromatichne chislo ne perevishuye 5 d 3 O 1 displaystyle frac 5d 3 O 1 Vzagali dlya bud yakogo grafa z virodzhennyam d ta maksimalnim stepenem D virodzhennya kvadratu grafa dorivnyuye O dD tozh dlya bagatoh z shilnih grafiv okrim planarnih tak samo hromatichne chislo kvadratu proporcijne D Nezvazhayuchi na te sho hromatichne chislo kvadratu neplanarnogo grafa mozhe buti proporcijnim u najgirshomu vipadku D vono bude menshim dlya grafiv z velikim obhvatom obmezhenih u comu vipadku O D2 log D Viznachennya minimalnoyi kilkosti koloriv neobhidnih dlya rozfarbuvannya kvadrat grafa ye NP skladnoyu zadacheyu navit u vipadku z planarnim grafom Gamiltonovist Kub kozhnogo zv yaznogo grafa obov yazkovo mistit Gamiltoniv cikl Ale kvadrat zv yaznogo grafa ne obov yazkovo ye gamiltonovim i ce ye NP povnoyu zadacheyu viyaviti chi ye kvadrat gamiltonovim Prote za teoremoyu Flyajshnera kvadrat 2 vershinno zv yaznogo grafa zavzhdi ye gamiltonovim Skladnist obchislennyaGraf stepeni k sho maye n vershin i m reber mozhe buti obchislenij za O mn chasu za dopomogoyu vikonannya poshuku v shirinu pochinayuchi z kozhnoyi vershini dlya viznachennya vidstani do vsih inshih vershin Yak alternativa yaksho A matricya sumizhnosti dlya grafa u yakomu zmineni usi nulovi elementi na golovnij diagonali na nenulevi to nenulevi elementi matrici Ak dayut matricyu sumizhnosti grafa stepenya k z cogo viplivaye sho pobudova stepeni k mozhe buti zdijsnena za toj chas sho znahoditsya u mezhah logarifmichnogo faktoru chasu dlya mnozhennya matric Ponyattya stepeni lista tisno pov yazano z k stepenem dereva indukovane listyam dereva G Cej klas grafiv znajshov zastosuvannya u filogenezi Bulo dosyagnuto pershogo tverdogo rezultatu Mayuchi graf virishiti chi ye kvadrat inshogo grafa NP povnoyu zadacheyu Krim togo NP povnoyu zadacheyu ye viznachiti chi ye graf stepenem inshogo grafa koli k 2 chi ye vin k stepenem dvochastinnogo grafa pri k gt 2 PrimitkiBondy Andrian Murty U S R 2008 Graph Theory English Springer Graduate Texts in Mathematics 244 s 82 ISBN 9781846289699 Weisstein Eric W Graph Power MathWorld Agnarsson Geir Magnus M 2000 Coloring powers of planar graphs San Francisco California Proceedings of the Eleventh Annual ACM SIAM Symposium on Discrete Algorithms SODA 00 s 654 662 Formann M Hagerup T Haralambides J Kaufmann M Leighton F Symvonis A Welzl E Woeginger G 1 zhovtnya 1993 Drawing Graphs in the Plane with High Resolution SIAM Journal on Computing T 22 5 s 1035 1052 doi 10 1137 0222063 ISSN 0097 5397 Procitovano 30 bereznya 2016 Kramer Florica Kramer Horst 6 lyutogo 2008 A survey on the distance colouring of graphs Discrete Mathematics T 308 2 3 s 422 426 doi 10 1016 j disc 2006 11 059 Procitovano 30 bereznya 2016 Molloy Michael Salavatipour Mohammad R 1 lipnya 2005 A bound on the chromatic number of the square of a planar graph Journal of Combinatorial Theory Series B T 94 2 s 189 213 doi 10 1016 j jctb 2004 12 005 Procitovano 30 bereznya 2016 Alon Noga Mohar Bojan 1 sichnya 2002 The Chromatic Number of Graph Powers Combinatorics Probability and Computing T 11 01 s 1 10 doi 10 1017 S0963548301004965 ISSN 1469 2163 Procitovano 30 bereznya 2016 Agnarsson ta Halldorsson 2000 list publications proving NP hardness for general graphs by McCormick 1983 and Lin and Skiena 1995 and for planar graphs by Ramanathan and Lloyd 1992 1993 Bondy ta Murty 2008 p 105 Underground Paris 1978 On graphs with Hamiltonian squares 21 3 323 doi 10 1016 0012 365X 78 90164 4 MR 0522906 Diestel Reinhard 2012 10 Hamiltonian cycles Graph Theory PDF vid corrected 4th electronic Nishimura Naomi Ragde Prabhakar Thilikos Dimitrios M 2002 On graph powers for leaf labeled trees Journal of Algorithms 42 1 69 108 doi 10 1006 jagm 2001 1195 MR 1874637 Motwani R Sudan M 1994 Computing roots of graphs is hard Discrete Applied Mathematics 54 81 88 doi 10 1016 0166 218x 94 00023 9 Le Van Bang Nguyen Ngoc Tuy 2010 Hardness results and efficient algorithms for graph powers Graph Theoretic Concepts in Computer Science 35th International Workshop WG 2009 Montpellier France June 24 26 2009 Revised Papers Lecture Notes in Computer Science t 5911 Berlin Springer s 238 249 doi 10 1007 978 3 642 11409 0 21 ISBN 978 3 642 11408 3 MR 2587715

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