Тут зібрані визначення термінів із теорії графів. Курсивом позначені посилання на терміни в цьому словнику (на цій сторінці).
Зміст: | А Б В Г Ґ Д Е Є Ж З И І Ї Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ю Я |
---|
А
- Автоморфізм — ізоморфізм графа із самим собою.
- Алгебрична зв'язність — друге з найменших власних значень матриці Кірхгофа графа.
Б
- Багаточастковий граф — граф, множину вершин якого можна розбити на k незалежних множин (часток).
- Біграф — див. двочастковий граф.
- Блок-схема із параметрами (v, k, λ) — покриття з кратністю λ повного графа на v вершинах повними графами на k вершинах.
- Блоковий граф — вид неорієнтованого графа, в якому кожна компонента двозв'язності (блок) є клікою.
В
- Валентність вершини — див. Степінь вершини
- Вершина, Вузол — базове поняття: точка, де можуть сходитися/розходитися ребра та/або дуги. Множина вершин графа G позначається V(G)
- Висяча вершина — вершина, степінь якої дорівнює 1 (тобто )
- Вага ребра — значення, поставлено у відповідність даному ребру зваженого графа. Зазвичай вага — дійсне число, в такому випадку його можна інтерпретувати як «довжину» ребра.
- Відстань між двома вершинами графа — найменша довжина шляху, що з'єднує ці вершини.
- — граф, в якому ребра, що виходять з кожної вершини, однозначно пронумеровані, починаючи з 1. Ребра вважаються впорядкованими в порядку зростання номерів. При графічному представленні часто ребра вважаються впорядкованими в порядку певного стандартного обходу (наприклад, проти годинникової стрілки).
- Вузол — те саме, що і Вершина.
Г
- Гамільтонів граф — граф, в якому є гамільтонів цикл.
- Гамільтонів шлях — простий шлях в графі, що містить всі вершини графа точно по одному разу.
- Гамільтонів цикл — простий цикл в графі, що містить всі вершини графа точно по одному разу.
- Гармонійне розфарбування — це (правильне) розфарбування вершин, за якого будь-яка пара кольорів з'являється на суміжних вершинах не більше одного разу.
- Геометрична реалізація — фігура, вершинам якої відповідають вершини графа, ребрам — ребра графа, і ребра у фігурі поєднують вершини, що відповідають вершинам в графі.
- Геометричний граф — плоска фігура з вершин — точок площини і ребер — ліній, що з'єднують деякі пари вершин. Може зображати багатьма способами будь-який граф.
- Гіперграф — сукупність із множини вершин і множини гіперребер (підмножина n-го евклідового степеня множини вершин, тобто гіперребра об'єднують довільну кількість вершин).
- Гомеоморфні графи — графи, отримані з одного графа за допомогою послідовного підрозбиття ребер.
- — область, обмежена ребрами в плоскому графі, і така, що не містить всередині себе вершин і ребер графа. Зовнішня частина площини також утворює грань.
- Граф — базове поняття. Містить в собі множину вершин і множину ребер, що являє собою підмножину декартового добутку множини вершин (тобто кожне ребро з'єднує рівно дві вершини).
- Граф роду g — граф, який можна зобразити без перетинань на поверхні роду g і не можна зобразити без перетинань на жодній поверхні роду g-1.
Д
- Двоїстий граф. Граф А називається двоїстим до планарного графа В, якщо вершини графа А відповідають граням графа В, і дві вершини графа A з'єднані ребром тоді і тільки тоді, коли відповідні грані графа B мають хоча б одне спільне ребро.
- Двочастковий граф або дводольний граф (або біграф, або парний граф) — граф , такий що множина вершин V розбита на дві підмножини і , що не перетинаються, при чому кожне ребро E інцидентне вершині з і вершині з (тобто з'єднує вершину з з вершиною з ). Тобто, існує правильне разфарбування графа двома кольорами. Множини і називають «долями» двочасткового графа. Двочастковий граф називается «повним», якщо будь-які дві вершини з і виявляться суміжними. Якщо , , то повний двочастковий граф позначається .
- Деревний кістяк — кістякове піддерево графа , в якому відстань між будь-якою парою вершин не перевищує -разової відстані між ними у графі .
- Дерево — зв'язний граф, що не містить циклів.
- (Діаметр графа) — максимальна відстань між вершинами для всіх пар вершин. Відстань між вершинами — найменша кількість ребер шляху, що з'єднує дві вершини.
- Довжина маршрута — кількість ребер в маршруті (з повтореннями). Якщо маршрут , то довжина M дорівнює k (позначається ).
- Довжина шляху — кількість дуг шляху (або сума довжин його дуг, якщо останні задані). Так для шляху v1, v2, …, vn довжина дорівнює n-1.
- Доповнення графа — граф над тою самою множиною вершин, що і початковий, але вершини з'єднані ребрами тоді і тільки тоді, коли в початковому графі ребра немає.
- Дуга — орієнтоване ребро.
Е
- Евклідове мінімальне кістякове дерево
- Ейлерів граф — граф, в якому існує цикл, що містить усі ребра графа по одному разу, вершини можуть повторюватися.
- Ейлерів ланцюг (або Ейлерів цикл) — ланцюг (цикл), що містить всі ребра графа, вершини можуть повторюватися.
- Екстремальна теорія графів
- Ексцентриситет вершини — максимальна відстань від заданої вершини до будь-якої іншої.
- Елементарний шлях — шлях, вершини якого, за виключенням можливо, першої і останньої, різні. Іншими словами, простий шлях не проходить двічі через одну вершину, але може починатися і закінчуватися в тій самій вершині, в такому випадку він називається циклом (елементарним циклом).
- Елементарним стягуванням називається така процедура: беремо ребро (разом інцидентними йому вершинами вершинами, наприклад, u і v) і «стягуємо» його, тобто видаляємо ребро і ототожнюємо вершини u і v. Утворена вершина інцидентна ребрам, яким початково були інцидентні u або v крім видаленого.
З
- Зважений граф — граф, кожному ребру якого поставлено у відповідність деяке значення (вага ребра).
- Зв'язність. Дві вершини в графі зв'язні, якщо існує (простий) ланцюг, що їх з'єднує.
- Зв'язний граф — граф, в якому всі вершини зв'язані.
- Граф-зірка — повний двочастковий граф .
- Змішаний граф — граф, що містить як орієнтовані, так і неорієнтовані ребра.
І
- Ізольована вершина — вершина, степінь якої дорівнює 0 (тобто не існують ребра інцидентні до неї).
- Ізоморфізм. Два графи називаються ізоморфними, якщо існує перестановка вершин, при якій вони збігаються. Іншими словами, два графи називаються ізоморфними, якщо існує взаємооднозначна відповідність між їх вершинами і ребрами, така що зберігається суміжність та інцидентність.
- (K) — Ki = (ΣL)i / (ΣL)min, де ΣL — сума найкоротших віддалей вершини.
- Інтервальний граф — граф, вершини якого можуть бути поставлені у відповідність відрізкам на дійсній осі таким чином, що дві вершини інцидентні одному ребру тоді і тільки тоді, коли відрізки, що відповідають цим вершинам, перетинаються.
- Інцидентність — поняття, що використовується тільки для ребра і вершини: якщо — вершини, а — ребро, що їх з'єднує, тоді вершина і ребро e інцидентні, вершина і ребро e також інцидентні. Дві вершини (або два ребра) інцидентними бути не можуть. Для позначення найближчих вершин (ребер) використовується поняття суміжності.
К
- Каркасний підграф — підграф, що містить всі вершини[].
- Кінець нескінченного графа, це клас еквівалентності променів, в якому два промені еквівалентні, якщо існує третій промінь, який містить нескінченно багато вершин цих графів.
- Кістякове (каркасне) дерево зв'язного графа G=(V, E) це таке дерево T=(V, ET), що ET ⊆ E.
- Кістяковим (каркасним) лісом незв'язного графа G=(V, E) називають сукупність кістякових (каркасних) дерев компонент зв'язності графа G.
- Кліка — підмножина вершин графа, повністю з'єднаних кожна з кожною, тобто підграф, що являє собою повний граф.
- Клікова ширина — параметр, який описує структурну складність графа.
- Клікове дерево — див. Блоковий граф.
- Клікове число (Clique number) — число (G) вершин в найбільший кліці. Інші назви — густота, щільність.
- Максимальна кліка — кліка з максимально можливою кількістю вершин графа.
- Клітка — регулярний граф найменшого обхвату для заданого степеня вершин.
- Коефіцієнт сітчастості — інваріант планарних графів.
- Компонента зв'язності графа — деяка підмножина вершин графа така, що для будь-яких двох вершин із цієї множини існує шлях із однієї в іншу, і не існує шляху з вершини цієї множини в вершину не з цієї множини.
- Компонента сильної зв'язності графа, шар — максимальна множина вершин орієнтованого графа така, що для будь-яких двох вершин із цієї підмножини існує шлях як із першої в другу, так і навпаки.
- Конструктивний перерахунок графів — отримання повного списку графів у заданому класі.
- Контур — замкнений шлях в орграфі.
- Косе розбиття — розбиття вершин графа на дві підмножини у вигляді незв'язного породженого підграфа та доповнення.
- Коцикл — мінімальний розріз, мінімальна множина ребер, видалення якої робить граф незв'язним.
- Кратні ребра — декілька ребер, інцидентних одній і тій самій парі вершин. Зустрічаються в мультиграфах.
- Кубічний граф — регулярний граф степеня 3, тобто граф, в якому кожній вершині інцидентні рівно три ребра.
- k-дольний граф — граф G, у якого хроматичне число c(G)=k
Л
- Лама́нів граф з n вершинами — такий граф G, що, по-перше, для кожного k будь-який підграф графа G, що містить k вершин, має не більше, ніж 2k −3 ребра і, по-друге, граф G має рівно 2n −3 ребра.
- Лінійна деревність — найменша кількість лінійних лісів, на які можна розбити граф.
- Лінійний ліс — ліс, утворений з диз'юнктного об'єднання шляхів
- Ліс — неорієнтований граф без циклів. Компонентами зв'язності лісу є дерева.
- Ланцюг в графі — маршрут, всі ребра якого різні. Якщо всі вершини (а таким чином і ребра) різні, то такий ланцюг називається простим (елементарним). В ланцюзі вершини і називаються кінцями ланцюга. Ланцюг із кінцями u і v з'єднує вершини u і v. Ланцюг, що з'єднує вершини u і v позначається . Для орграфів ланцюг називається орланцюгом. В деяких джерелах простий ланцюг — ланцюг, ребра якого різні, що є слабкою умовою.
М
- Маршрут (теорія графів) в графі — послідовність вершин і ребер , що чергуються, в якій будь-які два сусідні елемента інцидентні. Якщо , то маршрут замкнений, інакше відкритий.
- Матриця досяжності орграфа — матриця, що містить інформацію про існування шляхів між вершинами орграфа.
- Матриця інцидентності графа — матриця, значення елементів якої характеризуються інцидентністю відповідних вершин графа (по вертикалі) та його ребер (по горизонталі). Для неорієнтованого графа елемент приймає значення 1, якщо вершина і ребро, що відповідають йому, інцидентні. Для орієнтованого графа елемент приймає значення 1, якщо інцидентна вершина є початок ребра, значення -1, якщо кінець; в інших випадках (в тому числі і для петель) значенню елемента присвоюється 0.
- Матриця суміжності графа — матриця, значення елементів якої характеризується суміжністю вершин графа. При цьому, значенню елемента матриці присвоюється кількість ребер, які з'єднують відповідні вершини (тобто які інцидентні обом вершинам). Петля вважається одразу двома з'єднаннями для вершини, тобто до значення елемента матриці в такому випадку треба додавати 2.
- Мережа — в принципі, те саме що і граф, хоча мережами зазвичай називають графи, вершини яких визначеним способом позначені.
- Мінімальний каркас (або Каркас мінімальної ваги, Мінімальне кістякове дерево) графа — ациклічна множина ребер в зв'язному, зваженому і неорієнтованому графі, що з'єднує між собою всі вершини цього графа, при цьому сума ваг усіх ребер у ньому мінімальна.
- Міст — ребро, видалення якої збільшує кількість компонент зв'язності. Рівнозначне визначення, ребро є мостом тоді і тільки тоді, коли вони не є частиною будь-якого циклу.
- Множина домінування — така множина вершин графа, що кожна вершина графа або належить їй, або суміжна деякій вершині, що належить множині домінування.
- Множина суміжності вершини v — множина вершин, суміжних із вершиною v. Позначається
- Мультиграф — граф, в якому існує пара вершин, що з'єднана більш ніж одним ребром (ненаправленим), або більше ніж двома дугами протилежних напрямків.
Н
- Граф найближчих сусідів
- в орграфі для вершини v — кількість дуг, що входять в вершину. Позначається .
- в орграфі для вершини v — кількість дуг, що виходять з вершини. Позначається .
- Направлений граф — орієнтований граф, в якому дві вершини з'єднуються не більше ніж однією дугою.
- — орієнтований граф без контурів.
- Незалежна множина вершин — (відома також як внутрішня стала множина) множина вершин графа G, така, що будь-які дві вершини в ній не суміжні (жодна пара вершин не з'єднана ребром).
- Незалежна множина називається максимальною по включенню, коли немає іншої незалежної множини, в яку вона б входила.
- Максимальною незалежною множиною називається незалежна множина з найбільшою кількістю вершин. Іншими словами, якщо Q це сім'я всіх незалежних множин графа G, то число a(G) = max |S| (де S належить Q) називається числом незалежності графа G, а множина S*, на якій цей максимум досягається, називається найбільшою незалежною множиною або максимальною незалежною множиною.
- Незалежна множина ребер — множина ребер графа G, така, що будь-які два ребра в ній не суміжні (жодна пара ребер не має спільної вершини).
- Нескінченний граф — це граф, який не є скінченним: він має нескінченно багато вершин, нескінченно багато ребер або те й інше разом. Див. також Скінченний граф.
- Нормований граф — орієнтований граф без циклів.
- Нуль-граф (цілком незв'язний граф, порожній граф) — регулярний граф степеня 0, тобто граф, що не містить ребер.
О
- Обхват — довжина найменшого циклу в графі.
- Ожина — для неорієнтованого графа G — сімейство зв'язних підграфів, які дотикаються один з одним: для будь-якої пари підграфів, які не мають спільних вершин, має існувати ребро, кінцеві вершини якого лежать у цих двох підграфах.
- Оточення — довжина найбільшого простого циклу в графі.
- Орграф, орієнтований граф G = (V, E) пара множин, в якій V — множина вершин (вузлів), E — множина дуг (орієнтованих ребер). Дуга — впорядкована пара вершин (v, w), в якій вершину v називають початком, а w — кінцем дуги. Можна сказати, що дуга v → w веде від вершини v до вершини w, при цьому вершина w суміжна з вершиною v.
П
- Парний граф — те саме, що і двочастковий граф.
- Петля — ребро, початок і кінець якого знаходяться в одній і тій самій вершині.
- Перетин графів (позначених графів і ) — граф , множина вершин якого є , а множина ребер — .
- — підрахунок числа неізоморфних графів в заданому класі (із заданими характеристиками).
- Переріз графа — множина ребер, видалення яких ділить граф на два ізольованих підграфи, один з яких, зокрема, може бути тривіальним графом.
- Граф перестановки — граф, вершини якого відповідають елементам перестановки, а ребра представляють пари елементів, порядок слідування яких змінився після перестановки.
- Периферійна вершина — це вершина з максимальним ексцентриситетом. У дереві це мусить бути лист.
- початкового графа — граф, що містить деяку підмножину вершин даного графа і всі ребра, інцидентні даній підмножині.
- Планарний граф — граф, що може бути намальований (укладений) на площині без перетину ребер. Ізоморфний плоскому графу, тобто, є графом із перетинами, але таким, що допускає плоску укладку, через це може відрізнятися від плоского графа зображенням на площині. Таким чином, зображення на площині плоского і планарного графів можуть відрізнятись.
- — геометричний граф, в якому жодні два ребра не мають спільних точок крім інцидентним їм обом вершинам (не перетинаються). Є укладеним графом на площині.
- Повне розфарбування
- Повним графом називається граф, в якому для кожної пари вершин , існує ребро, інцидентне і інцидентне (кожна вершина з'єднана ребром з будь-якою іншою вершиною).
- Повним двочастковим називається двочастковий граф, в якому кожна вершина одної підмножини з'єднана ребром з кожною вершиною іншої підмножини.
- Породжений підграф — підграф, породжений множиною вершин похідного графа.
- Порожній граф — див. нуль-граф.
- Потужність графа — найменше відношення кількості ребер, видалених із графа, до числа компонент, отриманих внаслідок такого видалення (зменшеного на 1).
- — розфарбування, при якому кожний кольоровий клас є незалежною множиною. Інакше кажучи, в правильному розфарбуванні будь-які дві суміжні вершини повинні мати різні кольори.
- Простий ланцюг — маршрут, в якому всі вершини різні.
- — граф, в якому немає кратних ребер і петель.
- Простий цикл — цикл, що не проходить двічі через одну вершину.
- — граф, що містить петлі.
- Псевдоліс — неорієнтований граф, у якому будь-яка зв'язна компонента має не більше одного циклу.
Р
- (Радіус графа) — мінімальний з (ексцентриситетів) вершин зв'язаного графа; вершина, на якій досягається цей мінімум називається центральною вершиною.
- Ребро графа (дуга графа) — базове поняття. Ребро з'єднує дві вершини графа.
- Регулярний граф — граф, всіх вершин якого рівні. Степінь регулярності є інваріантом графа і позначається . Для нерегулярних графів не визначено. Регулярні графи являють собою особливу складність для багатьох алгоритмів.
- Регулярний граф степеня 0 (цілком незв'язний граф, порожній граф, нуль-граф) — граф без ребер.
- Резистивна відстань
- — функція, що задана на вершинах орієнтовного графа.
- Розмічений граф — граф, для якого задана множина позначок S, функція розмітки вершин f: A → S і функція розмітки дуг g: R → S. Графічно ці функції представляються надписуванням позначок на вершинах і дугах. Множина позначок може поділятися на дві підмножини позначок вершин і дуг, що не перетинаються.
- Розріз — множина ребер, видалення якої робить граф незв'язним.
- Розфарбування графа — розбиття вершин на множини, що називаються пелюстками. Якщо при цьому немає двох суміжних вершин, що належать до одної множини (тобто всі суміжні вершини завжди різного кольору), то таке розфарбування називається правильним.
С
- Самодвоїстий граф — граф, ізоморфний своєму двоїстому графу.
- Сильна зв'язність. Дві вершини в орграфі сильно зв'язані, якщо існує шлях з однієї в другу і назад.
- Сильно зв'язаний орграф — орграф, в якому всі вершини сильно зв'язані.
- Сильно регулярний граф
- Скінченний граф — граф, який має скінченне число вершин і скінченну кількість ребер. Багато джерел припускають, що всі графи скінченні, явно не кажучи про це. Граф є локально скінченним, якщо кожна вершина має скінченне число інцидентних ребер. Див. також Нескінченний граф.
- Спектр графа — множина всіх власних значень матриці суміжності з урахуванням кратних ребер.
- Степінь вершини — кількість ребер графа G, що інцидентні вершині x. Позначається . Мінімальний степінь вершини графа G позначається . а максимальний — .
- Стягування ребра графа — заміна кінців ребра однією вершиною, сусідами нової вершини стають сусіди цих кінців. Граф можна стягнути до , якщо другий можна отримати послідовним стягуванням ребер першого.
- Суграф (частковий граф) початкового графа — граф, що містить всі вершини початкового графа і підмножину його ребер.
- Сума за клікою — операція, що забезпечує комбінацію двох графів склеюванням їх за клікою, подібно до зв'язної суми в топології.
- Суміжність — поняття, яке використовується по відношенню тільки до двох ребер або двох вершин: Два ребра, інцидентні одній вершині, називаються суміжними; дві вершини, інцидентні одному ребру, також називаються суміжними.
Т
- Тета — граф, що складається з об'єднання трьох шляхів, які не мають усередині спільних вершин, у яких кінцеві вершини одні й ті ж
- Тета-граф — вид геометричного кістяка.
- Товщина графа
- Тривіальний граф — граф, що складається з однієї вершини.
- Тріангуляція поверхні — укладка графа на поверхню, яка розбиває її на трикутні області; окремий випадок триангуляції.
- — граф, у якого можливий лише один єдиний автоморфізм — тотожний. Образно кажучи, тотожний граф — «абсолютно несиметричний» граф.
- Т-розфарбування
- Турнір — орієнтований граф, в якому кожна пара вершин з'єднана одним ребром.
У
- Укладення: граф укладається на поверхню, якщо його можливо намалювати на цій поверхні так, щоб ребра графа при цьому не перетинались. (Див. Планарний граф, Плоский граф.)
Ф
- n-фактор графа — регулярний кістяковий підграф ступені .
- n-факторизація графа — розбиття графа на незалежні n-фактори.
- Фактор-граф
Х
- Хроматичне число графа — мінімальна кількість кольорів, що необхідна для розфарбування вершин графа, при якому будь-які суміжні вершини розфарбовані в різні кольори.
- Хроматичний індекс графа — мінімальна кількість кольорів, що необхідна для розфарбування ребер графа, при якому будь-які суміжні ребра розфарбовані в різні кольори.
Ц
- Центр графа — множина всіх вершин з найменшим ексцентриситетом.
- Цикл — замкнений ланцюг. Для орграфів цикл називають контуром.
- Цикл (простий цикл) в орграфі — простий шлях довжини не менш ніж 1, який починається і закінчується в одній і тій самій вершині.
- Цикл Гамільтона — те саме, що і Гамільтонів цикл.
- Цикломатичне число графа — число компонент зв'язності графа плюс число ребер мінус число вершин.
- Цілком незв'язний граф (пустий граф, нуль-граф) — регулярний граф степеня 0, тобто граф без ребер.
Ч
- Частковий граф — те саме, що субграф та кістяковий підграф.
- Число домінування — найменша потужність множини домінування у графі.
- Число незалежності або число внутрішньої сті́йкості графа — це розмір найбільшої незалежної множини вершин у ньому.
Ш
- Шлях — див. маршрут. Шлях, в якому будь-яка вершина не зустрічається двічі, називається елементарним.
- Шлях в орграфі — послідовність вершин v1, v2, …, vn, для якої існують дуги v1 → v2, v2 → v3, …, vn-1 → vn. Кажуть, що шлях починається у вершині v1, проходить через вершини v2, v3, …, vn-1, і закінчується у вершині vn.
Я
- Граф Яо — вид геометричного кістяка.
Зміст: | …на початок | ||||||||||||||||||||||||||||
А | Б | В | Г | Ґ | Д | Е | Є | Ж | З | І | Ї | К | Л | М | Н | О | П | Р | С | Т | У | Ф | Х | Ц | Ч | Ш | Щ | Ю | Я |
Примітки
- Ю. Нікольский, В. Пасічник, Ю. Щербина. Дискретна математика. — К : BHV, 2007. — С. 368. — .
- Р.М. Трохимчук. Теорія графів. — Навчальний посібник для студентів факультету кібернетики. — К : РВЦ «Київський університет», 1998. — С. 24. — .
- В різних джерелах надають різні визначення маршруту, шляху, ланцюга, їх простоти та елементарності.
- J. A. Bondy. Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs). — Т. 303. — DOI:
Посилання
- Chris Caldwell Graph Theory Glossary
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Portal Matematika Tut zibrani viznachennya terminiv iz teoriyi grafiv Kursivom poznacheni posilannya na termini v comu slovniku na cij storinci Zmist A B V G G D E Ye Zh Z I I Yi J K L M N O P R S T U F H C Ch Sh Sh Yu Ya AAvtomorfizm izomorfizm grafa iz samim soboyu Algebrichna zv yaznist druge z najmenshih vlasnih znachen matrici Kirhgofa grafa BBagatochastkovij graf graf mnozhinu vershin yakogo mozhna rozbiti na k nezalezhnih mnozhin chastok Bigraf div dvochastkovij graf Blok shema iz parametrami v k l pokrittya z kratnistyu l povnogo grafa na v vershinah povnimi grafami na k vershinah Blokovij graf vid neoriyentovanogo grafa v yakomu kozhna komponenta dvozv yaznosti blok ye klikoyu VValentnist vershini div Stepin vershini Vershina Vuzol bazove ponyattya tochka de mozhut shoditisya rozhoditisya rebra ta abo dugi Mnozhina vershin grafa G poznachayetsya V G Visyacha vershina vershina stepin yakoyi dorivnyuye 1 tobto d v 1 displaystyle d v 1 Vaga rebra znachennya postavleno u vidpovidnist danomu rebru zvazhenogo grafa Zazvichaj vaga dijsne chislo v takomu vipadku jogo mozhna interpretuvati yak dovzhinu rebra Vidstan mizh dvoma vershinami grafa najmensha dovzhina shlyahu sho z yednuye ci vershini graf v yakomu rebra sho vihodyat z kozhnoyi vershini odnoznachno pronumerovani pochinayuchi z 1 Rebra vvazhayutsya vporyadkovanimi v poryadku zrostannya nomeriv Pri grafichnomu predstavlenni chasto rebra vvazhayutsya vporyadkovanimi v poryadku pevnogo standartnogo obhodu napriklad proti godinnikovoyi strilki Vuzol te same sho i Vershina GGamiltoniv graf graf v yakomu ye gamiltoniv cikl Gamiltoniv shlyah prostij shlyah v grafi sho mistit vsi vershini grafa tochno po odnomu razu Gamiltoniv cikl prostij cikl v grafi sho mistit vsi vershini grafa tochno po odnomu razu Garmonijne rozfarbuvannya ce pravilne rozfarbuvannya vershin za yakogo bud yaka para koloriv z yavlyayetsya na sumizhnih vershinah ne bilshe odnogo razu Geometrichna realizaciya figura vershinam yakoyi vidpovidayut vershini grafa rebram rebra grafa i rebra u figuri poyednuyut vershini sho vidpovidayut vershinam v grafi Geometrichnij graf ploska figura z vershin tochok ploshini i reber linij sho z yednuyut deyaki pari vershin Mozhe zobrazhati bagatma sposobami bud yakij graf Gipergraf sukupnist iz mnozhini vershin i mnozhini giperreber pidmnozhina n go evklidovogo stepenya mnozhini vershin tobto giperrebra ob yednuyut dovilnu kilkist vershin Gomeomorfni grafi grafi otrimani z odnogo grafa za dopomogoyu poslidovnogo pidrozbittya reber oblast obmezhena rebrami v ploskomu grafi i taka sho ne mistit vseredini sebe vershin i reber grafa Zovnishnya chastina ploshini takozh utvoryuye gran Graf bazove ponyattya Mistit v sobi mnozhinu vershin i mnozhinu reber sho yavlyaye soboyu pidmnozhinu dekartovogo dobutku mnozhini vershin tobto kozhne rebro z yednuye rivno dvi vershini Graf rodu g graf yakij mozhna zobraziti bez peretinan na poverhni rodu g i ne mozhna zobraziti bez peretinan na zhodnij poverhni rodu g 1 DDvoyistij graf Graf A nazivayetsya dvoyistim do planarnogo grafa V yaksho vershini grafa A vidpovidayut granyam grafa V i dvi vershini grafa A z yednani rebrom todi i tilki todi koli vidpovidni grani grafa B mayut hocha b odne spilne rebro Dvochastkovij graf abo dvodolnij graf abo bigraf abo parnij graf graf G V E displaystyle G V E takij sho mnozhina vershin V rozbita na dvi pidmnozhini V 1 displaystyle V 1 i V 2 displaystyle V 2 sho ne peretinayutsya pri chomu kozhne rebro E incidentne vershini z V 1 displaystyle V 1 i vershini z V 2 displaystyle V 2 tobto z yednuye vershinu z V 1 displaystyle V 1 z vershinoyu z V 2 displaystyle V 2 Tobto isnuye pravilne razfarbuvannya grafa dvoma kolorami Mnozhini V 1 displaystyle V 1 i V 2 displaystyle V 2 nazivayut dolyami dvochastkovogo grafa Dvochastkovij graf nazivaetsya povnim yaksho bud yaki dvi vershini z V 1 displaystyle V 1 i V 2 displaystyle V 2 viyavlyatsya sumizhnimi Yaksho V 1 a displaystyle left V 1 right a V 2 b displaystyle left V 2 right b to povnij dvochastkovij graf poznachayetsya K a b displaystyle K a b Derevnij kistyak kistyakove pidderevo T displaystyle T grafa G displaystyle G v yakomu vidstan mizh bud yakoyu paroyu vershin ne perevishuye k displaystyle k razovoyi vidstani mizh nimi u grafi G displaystyle G Derevo zv yaznij graf sho ne mistit cikliv Diametr grafa maksimalna vidstan mizh vershinami dlya vsih par vershin Vidstan mizh vershinami najmensha kilkist reber shlyahu sho z yednuye dvi vershini Dovzhina marshruta kilkist reber v marshruti z povtorennyami Yaksho marshrut M v 0 e 1 v 1 e 2 v 2 e k v k displaystyle M v 0 e 1 v 1 e 2 v 2 e k v k to dovzhina M dorivnyuye k poznachayetsya M k displaystyle left M right k Dovzhina shlyahu kilkist dug shlyahu abo suma dovzhin jogo dug yaksho ostanni zadani Tak dlya shlyahu v1 v2 vn dovzhina dorivnyuye n 1 Dopovnennya grafa graf nad toyu samoyu mnozhinoyu vershin sho i pochatkovij ale vershini z yednani rebrami todi i tilki todi koli v pochatkovomu grafi rebra nemaye Duga oriyentovane rebro EEvklidove minimalne kistyakove derevo Ejleriv graf graf v yakomu isnuye cikl sho mistit usi rebra grafa po odnomu razu vershini mozhut povtoryuvatisya Ejleriv lancyug abo Ejleriv cikl lancyug cikl sho mistit vsi rebra grafa vershini mozhut povtoryuvatisya Ekstremalna teoriya grafiv Ekscentrisitet vershini maksimalna vidstan vid zadanoyi vershini do bud yakoyi inshoyi Elementarnij shlyah shlyah vershini yakogo za viklyuchennyam mozhlivo pershoyi i ostannoyi rizni Inshimi slovami prostij shlyah ne prohodit dvichi cherez odnu vershinu ale mozhe pochinatisya i zakinchuvatisya v tij samij vershini v takomu vipadku vin nazivayetsya ciklom elementarnim ciklom Elementarnim styaguvannyam nazivayetsya taka procedura beremo rebro razom incidentnimi jomu vershinami vershinami napriklad u i v i styaguyemo jogo tobto vidalyayemo rebro i ototozhnyuyemo vershini u i v Utvorena vershina incidentna rebram yakim pochatkovo buli incidentni u abo v krim vidalenogo ZZvazhenij graf graf kozhnomu rebru yakogo postavleno u vidpovidnist deyake znachennya vaga rebra Zv yaznist Dvi vershini v grafi zv yazni yaksho isnuye prostij lancyug sho yih z yednuye Zv yaznij graf graf v yakomu vsi vershini zv yazani Graf zirka povnij dvochastkovij graf K 1 b displaystyle K 1 b Zmishanij graf graf sho mistit yak oriyentovani tak i neoriyentovani rebra IIzolovana vershina vershina stepin yakoyi dorivnyuye 0 tobto ne isnuyut rebra incidentni do neyi Izomorfizm Dva grafi nazivayutsya izomorfnimi yaksho isnuye perestanovka vershin pri yakij voni zbigayutsya Inshimi slovami dva grafi nazivayutsya izomorfnimi yaksho isnuye vzayemoodnoznachna vidpovidnist mizh yih vershinami i rebrami taka sho zberigayetsya sumizhnist ta incidentnist K Ki SL i SL min de SL suma najkorotshih viddalej vershini Intervalnij graf graf vershini yakogo mozhut buti postavleni u vidpovidnist vidrizkam na dijsnij osi takim chinom sho dvi vershini incidentni odnomu rebru todi i tilki todi koli vidrizki sho vidpovidayut cim vershinam peretinayutsya Incidentnist ponyattya sho vikoristovuyetsya tilki dlya rebra i vershini yaksho v 1 v 2 displaystyle v 1 v 2 vershini a e v 1 v 2 displaystyle e v 1 v 2 rebro sho yih z yednuye todi vershina v 1 displaystyle v 1 i rebro e incidentni vershina v 2 displaystyle v 2 i rebro e takozh incidentni Dvi vershini abo dva rebra incidentnimi buti ne mozhut Dlya poznachennya najblizhchih vershin reber vikoristovuyetsya ponyattya sumizhnosti KKarkasnij pidgraf pidgraf sho mistit vsi vershini dzherelo Kinec neskinchennogo grafa ce klas ekvivalentnosti promeniv v yakomu dva promeni ekvivalentni yaksho isnuye tretij promin yakij mistit neskinchenno bagato vershin cih grafiv Kistyakove karkasne derevo zv yaznogo grafa G V E ce take derevo T V ET sho ET E Kistyakovim karkasnim lisom nezv yaznogo grafa G V E nazivayut sukupnist kistyakovih karkasnih derev komponent zv yaznosti grafa G Klika pidmnozhina vershin grafa povnistyu z yednanih kozhna z kozhnoyu tobto pidgraf sho yavlyaye soboyu povnij graf Klikova shirina parametr yakij opisuye strukturnu skladnist grafa Klikove derevo div Blokovij graf Klikove chislo Clique number chislo G vershin v najbilshij klici Inshi nazvi gustota shilnist Maksimalna klika klika z maksimalno mozhlivoyu kilkistyu vershin grafa Klitka regulyarnij graf najmenshogo obhvatu dlya zadanogo stepenya vershin Koeficiyent sitchastosti invariant planarnih grafiv Komponenta zv yaznosti grafa deyaka pidmnozhina vershin grafa taka sho dlya bud yakih dvoh vershin iz ciyeyi mnozhini isnuye shlyah iz odniyeyi v inshu i ne isnuye shlyahu z vershini ciyeyi mnozhini v vershinu ne z ciyeyi mnozhini Komponenta silnoyi zv yaznosti grafa shar maksimalna mnozhina vershin oriyentovanogo grafa taka sho dlya bud yakih dvoh vershin iz ciyeyi pidmnozhini isnuye shlyah yak iz pershoyi v drugu tak i navpaki Konstruktivnij pererahunok grafiv otrimannya povnogo spisku grafiv u zadanomu klasi Kontur zamknenij shlyah v orgrafi Kose rozbittya rozbittya vershin grafa na dvi pidmnozhini u viglyadi nezv yaznogo porodzhenogo pidgrafa ta dopovnennya Kocikl minimalnij rozriz minimalna mnozhina reber vidalennya yakoyi robit graf nezv yaznim Kratni rebra dekilka reber incidentnih odnij i tij samij pari vershin Zustrichayutsya v multigrafah Kubichnij graf regulyarnij graf stepenya 3 tobto graf v yakomu kozhnij vershini incidentni rivno tri rebra k dolnij graf graf G u yakogo hromatichne chislo c G kLLama niv graf z n vershinami takij graf G sho po pershe dlya kozhnogo k bud yakij pidgraf grafa G sho mistit k vershin maye ne bilshe nizh 2k 3 rebra i po druge graf G maye rivno 2n 3 rebra Linijna derevnist najmensha kilkist linijnih lisiv na yaki mozhna rozbiti graf Linijnij lis lis utvorenij z diz yunktnogo ob yednannya shlyahiv Lis neoriyentovanij graf bez cikliv Komponentami zv yaznosti lisu ye dereva Lancyug v grafi marshrut vsi rebra yakogo rizni Yaksho vsi vershini a takim chinom i rebra rizni to takij lancyug nazivayetsya prostim elementarnim V lancyuzi v 0 e 1 e k v k displaystyle v 0 e 1 e k v k vershini v 0 displaystyle v 0 i v k displaystyle v k nazivayutsya kincyami lancyuga Lancyug iz kincyami u i v z yednuye vershini u i v Lancyug sho z yednuye vershini u i v poznachayetsya u v displaystyle left langle u v right rangle Dlya orgrafiv lancyug nazivayetsya orlancyugom V deyakih dzherelah prostij lancyug lancyug rebra yakogo rizni sho ye slabkoyu umovoyu MMarshrut teoriya grafiv v grafi poslidovnist vershin i reber v 0 e 1 v 1 e 2 v 2 e k v k displaystyle v 0 e 1 v 1 e 2 v 2 e k v k sho cherguyutsya v yakij bud yaki dva susidni elementa incidentni Yaksho v 0 v k displaystyle v 0 v k to marshrut zamknenij inakshe vidkritij Matricya dosyazhnosti orgrafa matricya sho mistit informaciyu pro isnuvannya shlyahiv mizh vershinami orgrafa Matricya incidentnosti grafa matricya znachennya elementiv yakoyi harakterizuyutsya incidentnistyu vidpovidnih vershin grafa po vertikali ta jogo reber po gorizontali Dlya neoriyentovanogo grafa element prijmaye znachennya 1 yaksho vershina i rebro sho vidpovidayut jomu incidentni Dlya oriyentovanogo grafa element prijmaye znachennya 1 yaksho incidentna vershina ye pochatok rebra znachennya 1 yaksho kinec v inshih vipadkah v tomu chisli i dlya petel znachennyu elementa prisvoyuyetsya 0 Matricya sumizhnosti grafa matricya znachennya elementiv yakoyi harakterizuyetsya sumizhnistyu vershin grafa Pri comu znachennyu elementa matrici prisvoyuyetsya kilkist reber yaki z yednuyut vidpovidni vershini tobto yaki incidentni obom vershinam Petlya vvazhayetsya odrazu dvoma z yednannyami dlya vershini tobto do znachennya elementa matrici v takomu vipadku treba dodavati 2 Merezha v principi te same sho i graf hocha merezhami zazvichaj nazivayut grafi vershini yakih viznachenim sposobom poznacheni Minimalnij karkas abo Karkas minimalnoyi vagi Minimalne kistyakove derevo grafa aciklichna mnozhina reber v zv yaznomu zvazhenomu i neoriyentovanomu grafi sho z yednuye mizh soboyu vsi vershini cogo grafa pri comu suma vag usih reber u nomu minimalna Mist rebro vidalennya yakoyi zbilshuye kilkist komponent zv yaznosti Rivnoznachne viznachennya rebro ye mostom todi i tilki todi koli voni ne ye chastinoyu bud yakogo ciklu Mnozhina dominuvannya taka mnozhina vershin grafa sho kozhna vershina grafa abo nalezhit yij abo sumizhna deyakij vershini sho nalezhit mnozhini dominuvannya Mnozhina sumizhnosti vershini v mnozhina vershin sumizhnih iz vershinoyu v Poznachayetsya G v displaystyle Gamma v Multigraf graf v yakomu isnuye para vershin sho z yednana bilsh nizh odnim rebrom nenapravlenim abo bilshe nizh dvoma dugami protilezhnih napryamkiv NGraf najblizhchih susidiv v orgrafi dlya vershini v kilkist dug sho vhodyat v vershinu Poznachayetsya d v displaystyle d v v orgrafi dlya vershini v kilkist dug sho vihodyat z vershini Poznachayetsya d v displaystyle d v Napravlenij graf oriyentovanij graf v yakomu dvi vershini z yednuyutsya ne bilshe nizh odniyeyu dugoyu oriyentovanij graf bez konturiv Nezalezhna mnozhina vershin vidoma takozh yak vnutrishnya stala mnozhina mnozhina vershin grafa G taka sho bud yaki dvi vershini v nij ne sumizhni zhodna para vershin ne z yednana rebrom Nezalezhna mnozhina nazivayetsya maksimalnoyu po vklyuchennyu koli nemaye inshoyi nezalezhnoyi mnozhini v yaku vona b vhodila Maksimalnoyu nezalezhnoyu mnozhinoyu nazivayetsya nezalezhna mnozhina z najbilshoyu kilkistyu vershin Inshimi slovami yaksho Q ce sim ya vsih nezalezhnih mnozhin grafa G to chislo a G max S de S nalezhit Q nazivayetsya chislom nezalezhnosti grafa G a mnozhina S na yakij cej maksimum dosyagayetsya nazivayetsya najbilshoyu nezalezhnoyu mnozhinoyu abo maksimalnoyu nezalezhnoyu mnozhinoyu Nezalezhna mnozhina reber mnozhina reber grafa G taka sho bud yaki dva rebra v nij ne sumizhni zhodna para reber ne maye spilnoyi vershini Neskinchennij graf ce graf yakij ne ye skinchennim vin maye neskinchenno bagato vershin neskinchenno bagato reber abo te j inshe razom Div takozh Skinchennij graf Normovanij graf oriyentovanij graf bez cikliv Nul graf cilkom nezv yaznij graf porozhnij graf regulyarnij graf stepenya 0 tobto graf sho ne mistit reber OObhvat dovzhina najmenshogo ciklu v grafi Ozhina dlya neoriyentovanogo grafa G simejstvo zv yaznih pidgrafiv yaki dotikayutsya odin z odnim dlya bud yakoyi pari pidgrafiv yaki ne mayut spilnih vershin maye isnuvati rebro kincevi vershini yakogo lezhat u cih dvoh pidgrafah Otochennya dovzhina najbilshogo prostogo ciklu v grafi Orgraf oriyentovanij graf G V E para mnozhin v yakij V mnozhina vershin vuzliv E mnozhina dug oriyentovanih reber Duga vporyadkovana para vershin v w v yakij vershinu v nazivayut pochatkom a w kincem dugi Mozhna skazati sho duga v w vede vid vershini v do vershini w pri comu vershina w sumizhna z vershinoyu v PParnij graf te same sho i dvochastkovij graf Petlya rebro pochatok i kinec yakogo znahodyatsya v odnij i tij samij vershini Peretin grafiv poznachenih grafiv G 1 X 1 U 1 displaystyle G 1 X 1 U 1 i G 2 X 2 U 2 displaystyle G 2 X 2 U 2 graf G 1 G 2 displaystyle G 1 cap G 2 mnozhina vershin yakogo ye X 1 X 2 displaystyle X 1 cap X 2 a mnozhina reber U U 1 U 2 displaystyle U U 1 cap U 2 pidrahunok chisla neizomorfnih grafiv v zadanomu klasi iz zadanimi harakteristikami Pereriz grafa mnozhina reber vidalennya yakih dilit graf na dva izolovanih pidgrafi odin z yakih zokrema mozhe buti trivialnim grafom Graf perestanovki graf vershini yakogo vidpovidayut elementam perestanovki a rebra predstavlyayut pari elementiv poryadok sliduvannya yakih zminivsya pislya perestanovki Periferijna vershina ce vershina z maksimalnim ekscentrisitetom U derevi ce musit buti list pochatkovogo grafa graf sho mistit deyaku pidmnozhinu vershin danogo grafa i vsi rebra incidentni danij pidmnozhini Planarnij graf graf sho mozhe buti namalovanij ukladenij na ploshini bez peretinu reber Izomorfnij ploskomu grafu tobto ye grafom iz peretinami ale takim sho dopuskaye plosku ukladku cherez ce mozhe vidriznyatisya vid ploskogo grafa zobrazhennyam na ploshini Takim chinom zobrazhennya na ploshini ploskogo i planarnogo grafiv mozhut vidriznyatis geometrichnij graf v yakomu zhodni dva rebra ne mayut spilnih tochok krim incidentnim yim obom vershinam ne peretinayutsya Ye ukladenim grafom na ploshini Povne rozfarbuvannya Povnim grafom nazivayetsya graf v yakomu dlya kozhnoyi pari vershin v 1 v 2 displaystyle v 1 v 2 isnuye rebro incidentne v 1 displaystyle v 1 i incidentne v 2 displaystyle v 2 kozhna vershina z yednana rebrom z bud yakoyu inshoyu vershinoyu Povnim dvochastkovim nazivayetsya dvochastkovij graf v yakomu kozhna vershina odnoyi pidmnozhini z yednana rebrom z kozhnoyu vershinoyu inshoyi pidmnozhini Porodzhenij pidgraf pidgraf porodzhenij mnozhinoyu vershin pohidnogo grafa Porozhnij graf div nul graf Potuzhnist grafa najmenshe vidnoshennya kilkosti reber vidalenih iz grafa do chisla komponent otrimanih vnaslidok takogo vidalennya zmenshenogo na 1 rozfarbuvannya pri yakomu kozhnij kolorovij klas ye nezalezhnoyu mnozhinoyu Inakshe kazhuchi v pravilnomu rozfarbuvanni bud yaki dvi sumizhni vershini povinni mati rizni kolori Prostij lancyug marshrut v yakomu vsi vershini rizni graf v yakomu nemaye kratnih reber i petel Prostij cikl cikl sho ne prohodit dvichi cherez odnu vershinu graf sho mistit petli Psevdolis neoriyentovanij graf u yakomu bud yaka zv yazna komponenta maye ne bilshe odnogo ciklu RRadius grafa minimalnij z ekscentrisitetiv vershin zv yazanogo grafa vershina na yakij dosyagayetsya cej minimum nazivayetsya centralnoyu vershinoyu Rebro grafa duga grafa bazove ponyattya Rebro z yednuye dvi vershini grafa Regulyarnij graf graf vsih vershin yakogo rivni Stepin regulyarnosti ye invariantom grafa i poznachayetsya r G displaystyle r G Dlya neregulyarnih grafiv r G displaystyle r G ne viznacheno Regulyarni grafi yavlyayut soboyu osoblivu skladnist dlya bagatoh algoritmiv Regulyarnij graf stepenya 0 cilkom nezv yaznij graf porozhnij graf nul graf graf bez reber Rezistivna vidstan funkciya sho zadana na vershinah oriyentovnogo grafa Rozmichenij graf graf dlya yakogo zadana mnozhina poznachok S funkciya rozmitki vershin f A S i funkciya rozmitki dug g R S Grafichno ci funkciyi predstavlyayutsya nadpisuvannyam poznachok na vershinah i dugah Mnozhina poznachok mozhe podilyatisya na dvi pidmnozhini poznachok vershin i dug sho ne peretinayutsya Rozriz mnozhina reber vidalennya yakoyi robit graf nezv yaznim Rozfarbuvannya grafa rozbittya vershin na mnozhini sho nazivayutsya pelyustkami Yaksho pri comu nemaye dvoh sumizhnih vershin sho nalezhat do odnoyi mnozhini tobto vsi sumizhni vershini zavzhdi riznogo koloru to take rozfarbuvannya nazivayetsya pravilnim SSamodvoyistij graf graf izomorfnij svoyemu dvoyistomu grafu Silna zv yaznist Dvi vershini v orgrafi silno zv yazani yaksho isnuye shlyah z odniyeyi v drugu i nazad Silno zv yazanij orgraf orgraf v yakomu vsi vershini silno zv yazani Silno regulyarnij graf Skinchennij graf graf yakij maye skinchenne chislo vershin i skinchennu kilkist reber Bagato dzherel pripuskayut sho vsi grafi skinchenni yavno ne kazhuchi pro ce Graf ye lokalno skinchennim yaksho kozhna vershina maye skinchenne chislo incidentnih reber Div takozh Neskinchennij graf Spektr grafa mnozhina vsih vlasnih znachen matrici sumizhnosti z urahuvannyam kratnih reber Stepin vershini kilkist reber grafa G sho incidentni vershini x Poznachayetsya d x displaystyle d x Minimalnij stepin vershini grafa G poznachayetsya d G displaystyle delta G a maksimalnij D G displaystyle Delta G Styaguvannya rebra grafa zamina kinciv rebra odniyeyu vershinoyu susidami novoyi vershini stayut susidi cih kinciv Graf G 1 displaystyle G 1 mozhna styagnuti do G 2 displaystyle G 2 yaksho drugij mozhna otrimati poslidovnim styaguvannyam reber pershogo Sugraf chastkovij graf pochatkovogo grafa graf sho mistit vsi vershini pochatkovogo grafa i pidmnozhinu jogo reber Suma za klikoyu operaciya sho zabezpechuye kombinaciyu dvoh grafiv skleyuvannyam yih za klikoyu podibno do zv yaznoyi sumi v topologiyi Sumizhnist ponyattya yake vikoristovuyetsya po vidnoshennyu tilki do dvoh reber abo dvoh vershin Dva rebra incidentni odnij vershini nazivayutsya sumizhnimi dvi vershini incidentni odnomu rebru takozh nazivayutsya sumizhnimi TTeta graf sho skladayetsya z ob yednannya troh shlyahiv yaki ne mayut useredini spilnih vershin u yakih kincevi vershini odni j ti zh Teta graf vid geometrichnogo kistyaka Tovshina grafa Trivialnij graf graf sho skladayetsya z odniyeyi vershini Triangulyaciya poverhni ukladka grafa na poverhnyu yaka rozbivaye yiyi na trikutni oblasti okremij vipadok triangulyaciyi graf u yakogo mozhlivij lishe odin yedinij avtomorfizm totozhnij Obrazno kazhuchi totozhnij graf absolyutno nesimetrichnij graf T rozfarbuvannya Turnir oriyentovanij graf v yakomu kozhna para vershin z yednana odnim rebrom UUkladennya graf ukladayetsya na poverhnyu yaksho jogo mozhlivo namalyuvati na cij poverhni tak shob rebra grafa pri comu ne peretinalis Div Planarnij graf Ploskij graf Fn faktor grafa regulyarnij kistyakovij pidgraf stupeni n displaystyle n n faktorizaciya grafa rozbittya grafa na nezalezhni n faktori Faktor grafHHromatichne chislo grafa minimalna kilkist koloriv sho neobhidna dlya rozfarbuvannya vershin grafa pri yakomu bud yaki sumizhni vershini rozfarbovani v rizni kolori Hromatichnij indeks grafa minimalna kilkist koloriv sho neobhidna dlya rozfarbuvannya reber grafa pri yakomu bud yaki sumizhni rebra rozfarbovani v rizni kolori CCentr grafa mnozhina vsih vershin z najmenshim ekscentrisitetom Cikl zamknenij lancyug Dlya orgrafiv cikl nazivayut konturom Cikl prostij cikl v orgrafi prostij shlyah dovzhini ne mensh nizh 1 yakij pochinayetsya i zakinchuyetsya v odnij i tij samij vershini Cikl Gamiltona te same sho i Gamiltoniv cikl Ciklomatichne chislo grafa chislo komponent zv yaznosti grafa plyus chislo reber minus chislo vershin Cilkom nezv yaznij graf pustij graf nul graf regulyarnij graf stepenya 0 tobto graf bez reber ChChastkovij graf te same sho subgraf ta kistyakovij pidgraf Chislo dominuvannya najmensha potuzhnist mnozhini dominuvannya u grafi Chislo nezalezhnosti abo chislo vnutrishnoyi sti jkosti grafa ce rozmir najbilshoyi nezalezhnoyi mnozhini vershin u nomu ShShlyah div marshrut Shlyah v yakomu bud yaka vershina ne zustrichayetsya dvichi nazivayetsya elementarnim Shlyah v orgrafi poslidovnist vershin v1 v2 vn dlya yakoyi isnuyut dugi v1 v2 v2 v3 vn 1 vn Kazhut sho shlyah pochinayetsya u vershini v1 prohodit cherez vershini v2 v3 vn 1 i zakinchuyetsya u vershini vn YaGraf Yao vid geometrichnogo kistyaka Zmist na pochatok A B V G G D E Ye Zh Z I Yi K L M N O P R S T U F H C Ch Sh Sh Yu YaPrimitkiYu Nikolskij V Pasichnik Yu Sherbina Diskretna matematika K BHV 2007 S 368 ISBN 978 966 552 201 0 R M Trohimchuk Teoriya grafiv Navchalnij posibnik dlya studentiv fakultetu kibernetiki K RVC Kiyivskij universitet 1998 S 24 ISBN 966 594 043 0 V riznih dzherelah nadayut rizni viznachennya marshrutu shlyahu lancyuga yih prostoti ta elementarnosti J A Bondy Graph theory and applications Proc Conf Western Michigan Univ Kalamazoo Mich 1972 dedicated to the memory of J W T Youngs T 303 DOI 10 1007 BFb0067356 PosilannyaChris Caldwell Graph Theory Glossary