Розмітка графа в математиці - це призначення міток, які традиційно подають цілими числами, реберам, вершинам, або ребрам і вершинам графа.
Формально, якщо дано граф G = (V, E), вершинна розмітка є функцією з множини вершин V у множину міток. Граф з такою функцією називають графом з розміткою вершин. Аналогічно, розмітка ребер є функцією зі множини ребер E в множину міток. У цьому випадку граф називають графом з розміткою ребер.
У разі, коли мітками ребер є елементи впорядкованої множини (тобто дійсні числа), розмітку можна називати зваженим графом.
Якщо не зазначено явно, термін розмітка графа зазвичай означає вершинну розмітку, за якої всі мітки різні. Такий граф еквівалентно можна розмітити послідовними цілими числами {1,…, |V|}, де |V| - число вершин графа. Для багатьох застосувань ребрам або вершинам надають мітки, що мають сенс у відповідній галузі. Наприклад, ребрам можна призначити ваги, що відповідають «ціні» проїзду між двома суміжними вершинами.
У наведеному вище визначенні під графом розуміють скінченний неорієнтований простий граф. Проте, поняття розмітки можна застосувати до всіх розширень і узагальнень графів. Наприклад, у теорії автоматів і теорії формальних мов зазвичай розглядають розмічені мультиграфи, тобто графи, в яких пару вершин можуть з'єднувати декілька помічених ребер.
Історія
Більшість розміток графів мають витоком розмітки, які навів Алекс Роза в статті 1967 року. Роза виділив три типи розмітки, які він назвав α-, β- і ρ-розмітками. β-розмітку пізніше С. В. Голомб перейменував на граціозну і ця назва стала популярним.
Окремі випадки
Граціозна розмітка
Граф називають граціозним, якщо його вершини розмічено числами від 0 до |E|, розміру графа, і ця розмітка породжує реберну розмітку від 1 до |E|. Для будь-якого ребра e мітка ребра дорівнює додатній різниці між мітками вершин цього ребра. Іншими словами, якщо ребро e інцидентне двом вершинам з мітками i і j, то ребро e отримує мітку |i − j|. Таким чином, граф G = (V, E) є граціозним тоді і тільки тоді, коли існує вкладення, яке породжує бієкцію з E в додатні цілі числа аж до |E|.
У своїй роботі Роза довів, що всі ейлерові цикли розміру, порівнянного з 1 або 2 ((за модулем) 4), граціозними не є. Які сімейства графів є граціозними, нині інтенсивно досліджується. Можливо, найвизначнішою недоведеною гіпотезою в галузі розмітки графів є гіпотеза Рінгеля — Коціга, яка стверджує, що всі дерева граціозні. Це доведено для всіх шляхів, гусениць і багатьох інших нескінченних сімейств дерев. Сам Коціг назвав спробу довести гіпотезу «порочною».
Реберна граціозна розмітка
Реберна граціозна розмітка простих графів (графів без петель і кратних ребер) з p вершинами і q ребрами — це розмітка ребер різними цілими числами з набору {1, …, q}, така, що розмітка вершин сумами міток суміжних ребер за модулем p включає всі значення від 0 до p − 1. Кажуть, що граф G реберно граціозний, якщо дозволяє реберну граціозну розмітку.
Реберну граціозну розмітку першим увів 1985 року С. Ло.
Необхідною умовою існування для графа реберної розмітки є умова Ло:
Гармонійна розмітка
Гармонійна розмітка графа G — це вкладення множини вершин графа G в групу цілих чисел (за модулем) k, де k — число ребер графа G, яке породжує бієкцію між ребрами графа G і числами за модулем k вибором як мітки ребра (x, y) суми міток двох вершин x, y (mod k). Гармонійний граф — це граф, що має гармонійну розмітку. Непарні цикли є гармонійними графами, як і граф Петерсена. Є гіпотеза, що всі дерева є гармонійними графами, якщо дозволити одну вершину використовувати повторно. Книга з сімома сторінками K1,7 × K2 є прикладом негармонійного графа.
Розфарбування графів
Розфарбування графа є підкласом розмітки графа. Вершинне розфарбування призначає різні мітки суміжним вершинам, реберне розфарбування призначає різні мітки суміжним ребрам.
Щаслива розмітка
Щаслива розмітка графа G — це призначення додатних цілих чисел вершинам графа G так, що, якщо S(v) означає суму міток сусідніх вершин вершини v, то S є розфарбуванням вершин графа G. Щасливе число графа G — це таке найменше k, що граф G має щасливу розмітку цілими числами {1, …, k}.
Примітки
- Weisstein, Eric W. Labeled graph(англ.) на сайті Wolfram MathWorld.
- Calderbank, 1995, с. 53.
- Developments in Language Theory, 2005.
- Gallian, 1998.
- Rosa.
- Vietri, 2008, с. 31–46.
- Lo, 1985, с. 231–241.
- Guy, 2004, с. 190–191.
- Gallian, 1998, с. Dynamic Survey 6.
- Czerwiński, Grytczuk, Ẓelazny, 2009, с. 1078–1081.
Література
- Different Aspects of Coding Theory / Robert Calderbank. — 1995. — Т. 50. — С. 53. — (Proceeding of symposia in applied mathematics) — .
- Joseph Gallian. A Dynamic Survey of Graph Labelings, 1996-2005 // . — The Electronic Journal of Combinatorics, 1998. — Т. 5, вип. 18. з джерела 8 листопада 2019. Процитовано 2 серпня 2021.
- Rosa A. On certain valuations of vertices in a graph.
- Rosa A. On certain valuations of the vertices of a graph // [1] — New York : Gordon and Breach, 1967. — P. 349–355. з джерела 2 серпня 2021
- / Clelia De Felice, Antonio Restivo (Eds.). — Springer, 2005. — С. 313. — .
- Sheng-Ping Lo. On edge-graceful labelings of graphs. Proc. Conf., Sundance/Utah 1985 // Congressus Numerantium. — 1985. — Т. 50. — С. 231–241.
- Andrea Vietri. Sailing towards, and then against, the graceful tree conjecture: some promiscuous results // Bull. Inst. Comb. Appl.. — 2008. — Т. 53. — С. 31–46. — ISSN 1183-1278.
- . C13 // Unsolved problems in number theory. — 3rd. — , 2004. — .
- Sebastian Czerwiński, Jarosław Grytczuk, Wiktor Ẓelazny. Lucky labelings of graphs // Inf. Process. Lett.. — 2009. — Т. 109, № 18. — С. 1078–1081.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Rozmitka grafa v matematici ce priznachennya mitok yaki tradicijno podayut cilimi chislami reberam vershinam abo rebram i vershinam grafa Formalno yaksho dano graf G V E vershinna rozmitka ye funkciyeyu z mnozhini vershin V u mnozhinu mitok Graf z takoyu funkciyeyu nazivayut grafom z rozmitkoyu vershin Analogichno rozmitka reber ye funkciyeyu zi mnozhini reber E v mnozhinu mitok U comu vipadku graf nazivayut grafom z rozmitkoyu reber U razi koli mitkami reber ye elementi vporyadkovanoyi mnozhini tobto dijsni chisla rozmitku mozhna nazivati zvazhenim grafom Yaksho ne zaznacheno yavno termin rozmitka grafa zazvichaj oznachaye vershinnu rozmitku za yakoyi vsi mitki rizni Takij graf ekvivalentno mozhna rozmititi poslidovnimi cilimi chislami 1 V de V chislo vershin grafa Dlya bagatoh zastosuvan rebram abo vershinam nadayut mitki sho mayut sens u vidpovidnij galuzi Napriklad rebram mozhna priznachiti vagi sho vidpovidayut cini proyizdu mizh dvoma sumizhnimi vershinami U navedenomu vishe viznachenni pid grafom rozumiyut skinchennij neoriyentovanij prostij graf Prote ponyattya rozmitki mozhna zastosuvati do vsih rozshiren i uzagalnen grafiv Napriklad u teoriyi avtomativ i teoriyi formalnih mov zazvichaj rozglyadayut rozmicheni multigrafi tobto grafi v yakih paru vershin mozhut z yednuvati dekilka pomichenih reber IstoriyaBilshist rozmitok grafiv mayut vitokom rozmitki yaki naviv Aleks Roza v statti 1967 roku Roza vidiliv tri tipi rozmitki yaki vin nazvav a b i r rozmitkami b rozmitku piznishe S V Golomb perejmenuvav na gracioznu i cya nazva stala populyarnim Okremi vipadkiGraciozna rozmitka Dokladnishe Graciozna rozmitka Graciozna rozmitka Mitki vershin pokazano chornimi ciframi mitki reber chervonimi Graf nazivayut gracioznim yaksho jogo vershini rozmicheno chislami vid 0 do E rozmiru grafa i cya rozmitka porodzhuye rebernu rozmitku vid 1 do E Dlya bud yakogo rebra e mitka rebra dorivnyuye dodatnij riznici mizh mitkami vershin cogo rebra Inshimi slovami yaksho rebro e incidentne dvom vershinam z mitkami i i j to rebro e otrimuye mitku i j Takim chinom graf G V E ye gracioznim todi i tilki todi koli isnuye vkladennya yake porodzhuye biyekciyu z E v dodatni cili chisla azh do E U svoyij roboti Roza doviv sho vsi ejlerovi cikli rozmiru porivnyannogo z 1 abo 2 za modulem 4 gracioznimi ne ye Yaki simejstva grafiv ye gracioznimi nini intensivno doslidzhuyetsya Mozhlivo najviznachnishoyu nedovedenoyu gipotezoyu v galuzi rozmitki grafiv ye gipoteza Ringelya Kociga yaka stverdzhuye sho vsi dereva graciozni Ce dovedeno dlya vsih shlyahiv gusenic i bagatoh inshih neskinchennih simejstv derev Sam Kocig nazvav sprobu dovesti gipotezu porochnoyu Reberna graciozna rozmitka Reberna graciozna rozmitka prostih grafiv grafiv bez petel i kratnih reber z p vershinami i q rebrami ce rozmitka reber riznimi cilimi chislami z naboru 1 q taka sho rozmitka vershin sumami mitok sumizhnih reber za modulem p vklyuchaye vsi znachennya vid 0 do p 1 Kazhut sho graf G reberno gracioznij yaksho dozvolyaye rebernu gracioznu rozmitku Rebernu gracioznu rozmitku pershim uviv 1985 roku S Lo Neobhidnoyu umovoyu isnuvannya dlya grafa rebernoyi rozmitki ye umova Lo q q 1 p p 1 2 mod p displaystyle q q 1 p p 1 2 mod p Garmonijna rozmitka Div takozh Garmonijne rozfarbuvannya Garmonijna rozmitka grafa G ce vkladennya mnozhini vershin grafa G v grupu cilih chisel za modulem k de k chislo reber grafa G yake porodzhuye biyekciyu mizh rebrami grafa G i chislami za modulem k viborom yak mitki rebra x y sumi mitok dvoh vershin x y mod k Garmonijnij graf ce graf sho maye garmonijnu rozmitku Neparni cikli ye garmonijnimi grafami yak i graf Petersena Ye gipoteza sho vsi dereva ye garmonijnimi grafami yaksho dozvoliti odnu vershinu vikoristovuvati povtorno Kniga z simoma storinkami K1 7 K2 ye prikladom negarmonijnogo grafa Rozfarbuvannya grafiv Korektne rozfarbuvannya vershin grafa najmenshim naborom koloriv troma Rozfarbuvannya grafa ye pidklasom rozmitki grafa Vershinne rozfarbuvannya priznachaye rizni mitki sumizhnim vershinam reberne rozfarbuvannya priznachaye rizni mitki sumizhnim rebram Shasliva rozmitka Shasliva rozmitka grafa G ce priznachennya dodatnih cilih chisel vershinam grafa G tak sho yaksho S v oznachaye sumu mitok susidnih vershin vershini v to S ye rozfarbuvannyam vershin grafa G Shaslive chislo grafa G ce take najmenshe k sho graf G maye shaslivu rozmitku cilimi chislami 1 k PrimitkiWeisstein Eric W Labeled graph angl na sajti Wolfram MathWorld Calderbank 1995 s 53 Developments in Language Theory 2005 Gallian 1998 Rosa Vietri 2008 s 31 46 Lo 1985 s 231 241 Guy 2004 s 190 191 Gallian 1998 s Dynamic Survey 6 Czerwinski Grytczuk Ẓelazny 2009 s 1078 1081 LiteraturaDifferent Aspects of Coding Theory Robert Calderbank 1995 T 50 S 53 Proceeding of symposia in applied mathematics ISBN 0 8218 0379 4 Joseph Gallian A Dynamic Survey of Graph Labelings 1996 2005 The Electronic Journal of Combinatorics 1998 T 5 vip 18 z dzherela 8 listopada 2019 Procitovano 2 serpnya 2021 Rosa A On certain valuations of vertices in a graph Rosa A On certain valuations of the vertices of a graph 1 New York Gordon and Breach 1967 P 349 355 z dzherela 2 serpnya 2021 Clelia De Felice Antonio Restivo Eds Springer 2005 S 313 ISBN 3 540 26546 5 Sheng Ping Lo On edge graceful labelings of graphs Proc Conf Sundance Utah 1985 Congressus Numerantium 1985 T 50 S 231 241 Andrea Vietri Sailing towards and then against the graceful tree conjecture some promiscuous results Bull Inst Comb Appl 2008 T 53 S 31 46 ISSN 1183 1278 C13 Unsolved problems in number theory 3rd Springer Verlag 2004 ISBN 0 387 20860 7 Sebastian Czerwinski Jaroslaw Grytczuk Wiktor Ẓelazny Lucky labelings of graphs Inf Process Lett 2009 T 109 18 S 1078 1081