Розмітка графа

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

Формально, якщо дано граф 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). Гармонійний граф — це граф, що має гармонійну розмітку. Непарні цикли є гармонійними графами, як і граф Петерсена. Є гіпотеза, що всі дерева є гармонійними графами, якщо дозволити одну вершину використовувати повторно. Книга з сімома сторінками K_1,7 × K₂ є прикладом негармонійного графа.

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

Коректне розфарбування вершин графа найменшим набором кольорів — трьома.

Розфарбування графа є підкласом розмітки графа. Вершинне розфарбування призначає різні мітки суміжним вершинам, реберне розфарбування призначає різні мітки суміжним ребрам.

Щаслива розмітка

Щаслива розмітка графа G — це призначення додатних цілих чисел вершинам графа G так, що, якщо S(v) означає суму міток сусідніх вершин вершини v, то S є розфарбуванням вершин графа G. Щасливе число графа G — це таке найменше k, що граф G має щасливу розмітку цілими числами {1, …, k}.

Примітки

1. Weisstein, Eric W. Labeled graph(англ.) на сайті Wolfram MathWorld.
2. Calderbank, 1995, с. 53.
3. Developments in Language Theory, 2005.
4. Gallian, 1998.
5. Rosa.
6. Vietri, 2008, с. 31–46.
7. Lo, 1985, с. 231–241.
8. Guy, 2004, с. 190–191.
9. Gallian, 1998, с. Dynamic Survey 6.
10. Czerwiński, Grytczuk, Ẓelazny, 2009, с. 1078–1081.

Література

• Different Aspects of Coding Theory / Robert Calderbank. — 1995. — Т. 50. — С. 53. — (Proceeding of symposia in applied mathematics) — ISBN 0-8218-0379-4.
• Joseph Gallian. A Dynamic Survey of Graph Labelings, 1996-2005 // Electronic Journal of Combinatorics. — 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
• Developments in Language Theory / Clelia De Felice, Antonio Restivo (Eds.). — Springer, 2005. — С. 313. — ISBN 3-540-26546-5.
• 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.
• Richard K. Guy. C13 // Unsolved problems in number theory. — 3rd. — Springer-Verlag, 2004. — ISBN 0-387-20860-7.
• Sebastian Czerwiński, Jarosław Grytczuk, Wiktor Ẓelazny. Lucky labelings of graphs // Inf. Process. Lett.. — 2009. — Т. 109, № 18. — С. 1078–1081.