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

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

Формально, якщо дано граф G = (V, E), вершинна розмітка є функцією з множини вершин V у множину міток. Граф з такою функцією називають графом з розміткою вершин. Аналогічно, розмітка ребер є функцією зі множини ребер E в множину міток. У цьому випадку граф називають графом з розміткою ребер.

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

Якщо не зазначено явно, термін розмітка графу зазвичай означає вершинну розмітку, за якої всі мітки різні. Такий граф еквівалентно можна розмітити послідовними цілими числами {1,…, |V|}, де |V| - число вершин графу[1]. Для багатьох застосувань ребрам або вершинам надають мітки, що мають сенс у відповідній галузі. Наприклад, ребрам можна призначити ваги, що відповідають «ціні» проїзду між двома суміжними вершинами[2].

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

Історія

Більшість розміток графів мають витоком розмітки, які навів Алекс Роза в статті 1967 року[4]. Роза виділив три типи розмітки, які він назвав α-, β- і ρ-розмітками[5]. β-розмітку пізніше С. В. Голомб перейменував на граціозну і ця назва стала популярним.

Окремі випадки

Граціозна розмітка

Граціозна розмітка. Мітки вершин показано чорними цифрами, мітки ребер — червоними.

Граф називають граціозним, якщо його вершини розмічено числами від 0 до |E|, розміру графу, і ця розмітка породжує реберну розмітку від 1 до |E|. Для будь-якого ребра e мітка ребра дорівнює додатній різниці між мітками вершин цього ребра. Іншими словами, якщо ребро e інцидентне двом вершинам з мітками i і j, то ребро e отримує мітку |ij|. Таким чином, граф G = (V, E) є граціозним тоді і тільки тоді, коли існує вкладення, яке породжує бієкцію з E в додатні цілі числа аж до |E|.

У своїй роботі Роза довів, що всі ейлерові цикли розміру, порівнянного з 1 або 2 (за модулем 4), граціозними не є. Які сімейства графів є граціозними, нині інтенсивно досліджується. Можливо, найвизначнішою недоведеною гіпотезою в галузі розмітки графів є гіпотеза Рінгеля — Коціга, яка стверджує, що всі дерева граціозні. Це доведено для всіх шляхів, гусениць і багатьох інших нескінченних сімейств дерев. Сам Коціг назвав спробу довести гіпотезу «порочною»[6].

Реберна граціозна розмітка

Реберна граціозна розмітка простих графів (графів без петель і кратних ребер) з p вершинами і q ребрами — це розмітка ребер різними цілими числами з набору {1, …, q}, така, що розмітка вершин сумами міток суміжних ребер за модулем p включає всі значення від 0 до p − 1. Кажуть, що граф G реберно граціозний, якщо дозволяє реберну граціозну розмітку.

Реберну граціозну розмітку першим увів 1985 року С. Ло[7].

Необхідною умовою існування для графу реберної розмітки є умова Ло:

Гармонійна розмітка

Гармонійна розмітка графу G — це вкладення множини вершин графу G в групу цілих чисел за модулем k, де k — число ребер графу G, яке породжує бієкцію між ребрами графу G і числами за модулем k вибором як мітки ребра (x, y) суми міток двох вершин x, y (mod k). Гармонійний граф — це граф, що має гармонійну розмітку. Непарні цикли є гармонійними графами, як і граф Петерсена. Є гіпотеза, що всі дерева є гармонійними графами, якщо дозволити одну вершину використовувати повторно[8]. Книга з сімома сторінками K1,7 × K2 є прикладом негармонійного графу[9].

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

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

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

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

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

Примітки

  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 (21 січня).
  • Rosa A. On certain valuations of vertices in a graph.
    • Rosa A. On certain valuations of the vertices of a graph // Theory of Graphs. — New York : Gordon and Breach, 1967. — P. 349–355.
  • 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 (21 січня). С. 231–241.
  • Andrea Vietri. Sailing towards, and then against, the graceful tree conjecture: some promiscuous results // Bull. Inst. Comb. Appl..  2008. Т. 53 (21 січня). С. 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 (21 січня). С. 1078–1081.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.