Розмітка графа
Розмітка графа в математиці - це призначення міток, які традиційно подають цілими числами, реберам, вершинам, або ребрам і вершинам графа[1].
Формально, якщо дано граф Шаблон:Nobr, вершинна розмітка є функцією з множини вершин V у множину міток. Граф з такою функцією називають графом з розміткою вершин. Аналогічно, розмітка ребер є функцією зі множини ребер E в множину міток. У цьому випадку граф називають графом з розміткою ребер.
У разі, коли мітками ребер є елементи впорядкованої множини (тобто дійсні числа), розмітку можна називати зваженим графом.
Якщо не зазначено явно, термін розмітка графа зазвичай означає вершинну розмітку, за якої всі мітки різні. Такий граф еквівалентно можна розмітити послідовними цілими числами {1,…, |V|}, де |V| - число вершин графа[1]. Для багатьох застосувань ребрам або вершинам надають мітки, що мають сенс у відповідній галузі. Наприклад, ребрам можна призначити ваги, що відповідають «ціні» проїзду між двома суміжними вершинамиШаблон:Sfn.
У наведеному вище визначенні під графом розуміють скінченний неорієнтований простий граф. Проте, поняття розмітки можна застосувати до всіх розширень і узагальнень графів. Наприклад, у теорії автоматів і теорії формальних мов зазвичай розглядають розмічені мультиграфи, тобто графи, в яких пару вершин можуть з'єднувати декілька помічених реберШаблон:Sfn.
Історія
Більшість розміток графів мають витоком розмітки, які навів Алекс Роза в статті 1967 рокуШаблон:Sfn. Роза виділив три типи розмітки, які він назвав α-, β- і ρ-розміткамиШаблон:Sfn. β-розмітку пізніше С. В. Голомб перейменував на граціозну і ця назва стала популярним.
Окремі випадки
Граціозна розмітка
Граф називають граціозним, якщо його вершини розмічено числами від 0 до |E|, розміру графа, і ця розмітка породжує реберну розмітку від 1 до |E|. Для будь-якого ребра e мітка ребра дорівнює додатній різниці між мітками вершин цього ребра. Іншими словами, якщо ребро e інцидентне двом вершинам з мітками i і j, то ребро e отримує мітку |i − j|. Таким чином, граф G = (V, E) є граціозним тоді і тільки тоді, коли існує вкладення, яке породжує бієкцію з E в додатні цілі числа аж до |E|.
У своїй роботі Роза довів, що всі ейлерові цикли розміру, порівнянного з 1 або 2 (за модулем 4), граціозними не є. Які сімейства графів є граціозними, нині інтенсивно досліджується. Можливо, найвизначнішою недоведеною гіпотезою в галузі розмітки графів є гіпотеза Рінгеля — Коціга, яка стверджує, що всі дерева граціозні. Це доведено для всіх шляхів, гусениць і багатьох інших нескінченних сімейств дерев. Сам Коціг назвав спробу довести гіпотезу «порочною»Шаблон:Sfn.
Реберна граціозна розмітка
Реберна граціозна розмітка простих графів (графів без петель і кратних ребер) з p вершинами і q ребрами — це розмітка ребер різними цілими числами з набору Шаблон:Nobr}, така, що розмітка вершин сумами міток суміжних ребер за модулем p включає всі значення від 0 до Шаблон:Nobr. Кажуть, що граф G реберно граціозний, якщо дозволяє реберну граціозну розмітку.
Реберну граціозну розмітку першим увів 1985 року С. ЛоШаблон:Sfn.
Необхідною умовою існування для графа реберної розмітки є умова Ло:
Гармонійна розмітка
Шаблон:Див. також Гармонійна розмітка графа G — це вкладення множини вершин графа G в групу цілих чисел за модулем k, де k — число ребер графа G, яке породжує бієкцію між ребрами графа G і числами за модулем k вибором як мітки ребра (x, y) суми міток двох вершин x, y (mod k). Гармонійний граф — це граф, що має гармонійну розмітку. Непарні цикли є гармонійними графами, як і граф Петерсена. Є гіпотеза, що всі дерева є гармонійними графами, якщо дозволити одну вершину використовувати повторноШаблон:Sfn. Книга з сімома сторінками Шаблон:Math є прикладом негармонійного графаШаблон:Sfn.
Розфарбування графів
Розфарбування графа є підкласом розмітки графа. Вершинне розфарбування призначає різні мітки суміжним вершинам, реберне розфарбування призначає різні мітки суміжним ребрам.
Щаслива розмітка
Щаслива розмітка графа G — це призначення додатних цілих чисел вершинам графа G так, що, якщо S(v) означає суму міток сусідніх вершин вершини v, то S є розфарбуванням вершин графа G. Щасливе число графа G — це таке найменше k, що граф G має щасливу розмітку цілими числами Шаблон:Nobr}Шаблон:Sfn.