розділ 2).
У розділі 4 даної дисертації розглядаються антимагічні реберні нумерації графів. Під нумерацією скінченного неорієнтованого графа G=(V, E), ?V?=n, |E|=q, розуміють однозначне відображення f: V > Z (або E > Z), де Z - скінченна множина, найчастіше її елементами є додатні або невід'ємні цілі числа. Нумерація f породжує реберну (або вершинну) нумерацію графа G. В залежності від розрізняють граціозні, досконалі, гармонійні, арифметичні, магічні, антимагічні та інші нумерації [47 ? 53].
Зокрема, за допомогою введеної А. Роса в 1967 році граціозної нумерації - ?-нумерації, було знайдено підхід до розв'язування гіпотези Рингеля, котра полягає в тому, що повний граф К2n+1 можна розкласти на 2n+1 підграфів, кожен з яких ізоморфний дереву з n ребрами. А. Роса визначає ?-нумерацію як граціозну нумерацію з додатковою властивістю, і ?-нумерація також пов'язана з вивченням розкладів графів. Для прикладу А. Роса показав, що якщо граф G з q ребрами має граціозну нумерацію, то для кожного натурального числа р повний граф К2qp+1 може бути розкладеним на копії графа G. Розв'язанню такого типу задач присвячено статті А. Коціга [25], А. Петренюка [39].
Природним узагальненням граціозних графів є k-граціозні графи, введені незалежно П. Слатером [54] у 1981 р. та Махео і Тюлером у 1982 р., сколемівсько-граціозні [55, 56] та інші. Потік робіт про нумерації не припиняється. Вводяться та досліджуються нові види нумерацій, поширюються області їх застосувань - кристалографія, радіолокація, астрономія, хімія, комунікаційні системи, теорія кодування та ін. Наприклад, граціозна нумерація знайшла практичне застосування в задачах про будову радіоастрономічних антен ?57?.
Серед нових видів нумерацій ? антимагічна реберна нумерація, запроваджена Н. Хартсфілд і Г. Рингелем у 1989 році. Граф з q ребрами - антимагічний, якщо ребрам ставляться у відповідність числа (мітки) 1, 2, ..., q таким чином, що вершина одержує мітку, рівну сумі міток ребер, інцидентних цій вершині, і всі ці суми попарно різні. Дослідження відбуваються в двох напрямах: встановлення антимагічності та пошук різних антимагічних нумерацій певного графа або класу графів. Н. Хартсфілд і Г. Рингель висловили гіпотезу, що довільне дерево порядку n (n >2) антимагічне, актуальну і на даний час. В 2000 році цю гіпотезу довели для повних m?арних дерев П. Чават та В. Крішна. В 1989 році Н. Хартсфілд і Г. Рингель також припустили, що для довільного звичайного скінченного зв'язного графа, відмінного від К2, існує антимагічна реберна нумерація. В 2004 році в ?58?, із застосуванням ймовірностних методів та аналітичних методів теорії чисел, доведено істинність цього припущення для всіх графів G з n вершинами і мінімальним степенем ?(G)=?(logn). Також доведено антимагічність графів G з n (n?4) вершинами і ?(G)?n-2 та повних двочасткових графів. В [59] показано антимагічність тороїдальних ґраток , крім цього встановлено, що G?Сn - антимагічний граф, якщо G - r-регулярний граф і r?1. Ц. Чен [60] довів антимагічність графів Сm?Pn та Pm?Pn. В даній роботі здійснено знаходження антимагічних реберних нумерацій для деяких класів дерев та певних видів графів.
Наведені факти свідчать про те, що проблеми, які виникли ще на початку ХІХ століття, поступово розв'язуються для все більш широких класів конфігурацій. Більше того, загальновідомі класичні задачі сьогодні набувають інших модифікацій та застосувань. Актуальними є питання існування 1-факторизацій графів, які виникають не тільки в теорії графів, а і при вивченні ґраток, скінченних топологій. Суттєву роль відіграють
1-факторизації графів при вивченні автоморфізмів деяких комбінаторних конфігурацій, зокрема ШСТ.
Можна відзначити, що розклади графів знаходять застосування при побудові ефективних кодів [61, 62], плануванні експериментів [63] і комунікаційних схем та в багатьох інших задачах [64]. Наприклад, такі практичні задачі [65], як відбір оптимального, у певному розумінні, комбінаторного об'єкта з множини існуючих; побудова та перевірка гіпотез про комбінаторні конструкції; цілеспрямований пошук хімічних сполук, найкращих механічних систем, ефективних кодів і т. п. пов'язані з конструктивним переліком комбінаторних конфігурацій.
Саме тому існує неперервний інтерес до задач про існування, побудову розкладів графів на підграфи заданих типів, перелік розкладів різних видів та знаходження нумерацій графів.
1.2. Необхідні поняття теорії графів
Означення 1.2.1. Графом G=(V, E) називається сукупність двох множин - скінченної непорожньої множини V, що містить n вершин, і множини E, що містить q неупорядкованих пар різних елементів множини V.
Кожну пару вершин з E називають ребром графа G. V ? множина вершин; E ? множина ребер, причому V??; E?V?V. Будемо розглядати тільки скінченні графи, тобто множина V передбачається скінченною.
Вершина v і ребро e=(v, u) інцидентні, коли вершина v є кінцем ребра е. Два ребра називаються суміжними, якщо вони інцидентні одній і тій самій вершині. Дві вершини, інцидентні деякому ребру, називаються суміжними. Множина вершин, суміжних з вершиною v, називається множиною суміжності вершини v (або околом вершини v).
Під об'єднанням двох графів G1=(V1, E1) і G=(V2, E2) розуміють граф G=(V1?V2, E1?E2).
Мультиграф це граф, в якому не допускаються петлі, але пари вершин можуть з'єднуватися більш ніж одним ребром; ці ребра називаються кратними. Петлею є ребро виду e=(u, u).
Означення 1.2.2. Степенем вершини vi у графі G називається число ребер, інцидентних цій вершині; це число позначатиметься deg(vi). Максимальний і мінімальний степені вершин у графі G позначаються символами ?(G) і ?(G), відповідно:
?(G)=maxdeg(vi), ?(G)=mindeg(vi).
Якщо степені всіх вершин графа рівні r, то граф називається регулярним (однорідним) степеня r : ?(G)=?(G)=r.
Означення 1.2.3. Маршрутом у графі G називається послідовність ребер та вершин, у якій вершини чергуються з ребрами, послідовність починається з вершини і закінчується вер