|
Розмітка графаРозмітка графа в математиці - це призначення міток, які традиційно подають цілими числами, реберам, вершинам, або ребрам і вершинам графа[1]. Формально, якщо дано граф G = (V, E), вершинна розмітка є функцією з множини вершин V у множину міток. Граф з такою функцією називають графом з розміткою вершин. Аналогічно, розмітка ребер є функцією зі множини ребер E в множину міток. У цьому випадку граф називають графом з розміткою ребер. У разі, коли мітками ребер є елементи впорядкованої множини (тобто дійсні числа), розмітку можна називати зваженим графом. Якщо не зазначено явно, термін розмітка графа зазвичай означає вершинну розмітку, за якої всі мітки різні. Такий граф еквівалентно можна розмітити послідовними цілими числами {1,…, |V|}, де |V| - число вершин графа[1]. Для багатьох застосувань ребрам або вершинам надають мітки, що мають сенс у відповідній галузі. Наприклад, ребрам можна призначити ваги, що відповідають «ціні» проїзду між двома суміжними вершинами[2]. У наведеному вище визначенні під графом розуміють скінченний неорієнтований простий граф. Проте, поняття розмітки можна застосувати до всіх розширень і узагальнень графів. Наприклад, у теорії автоматів і теорії формальних мов зазвичай розглядають розмічені мультиграфи, тобто графи, в яких пару вершин можуть з'єднувати декілька помічених ребер[3]. ІсторіяБільшість розміток графів мають витоком розмітки, які навів Алекс Роза в статті 1967 року[4]. Роза виділив три типи розмітки, які він назвав α-, β- і ρ-розмітками[5]. β-розмітку пізніше С. В. Голомб перейменував на граціозну і ця назва стала популярним. Окремі випадкиГраціозна розмітка Граф називають граціозним, якщо його вершини розмічено числами від 0 до |E|, розміру графа, і ця розмітка породжує реберну розмітку від 1 до |E|. Для будь-якого ребра e мітка ребра дорівнює додатній різниці між мітками вершин цього ребра. Іншими словами, якщо ребро e інцидентне двом вершинам з мітками i і j, то ребро e отримує мітку |i − j|. Таким чином, граф 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]. Примітки
Література
|
