Перегляд вихідного коду сторінки Словник термінів теорії графів

{{Портал|Математика}}
Тут зібрані визначення термінів із [[Теорія графів|теорії графів]]. Курсивом позначені посилання на терміни в цьому словнику (на цій сторінці).

{{АБВ}}

== А ==
* '''[[Автоморфізм]]'''&nbsp;— [[#І|ізоморфізм]] графа із самим собою.
* [[Алгебрична зв'язність]]&nbsp;— друге з найменших власних значень матриці Кірхгофа графа.

== Б ==
* '''[[Багаточастковий граф]]'''&nbsp;— граф, множину вершин якого можна розбити на ''k'' незалежних множин (часток).
* '''Біграф'''&nbsp;— див. ''[[двочастковий граф]]''.
* '''[[Блок-схема (математика)|Блок-схема]]''' із параметрами (v, k, λ)&nbsp;— покриття з кратністю λ ''[[Повний граф|повного графа]]'' на v вершинах повними графами на k вершинах.
* '''[[Блоковий граф]]'''&nbsp;— вид [[Неорієнтований граф|неорієнтованого графа]], в якому кожна компонента [[Зв'язність графів|двозв'язності]] (блок) є [[Кліка (теорія графів)|клікою]].

== В ==
* '''Валентність вершини'''&nbsp;— див. ''[[#С|Степінь вершини]]''
* '''[[Вершина (теорія графів)|Вершина]]''', '''Вузол'''&nbsp;— базове поняття: [[точка]], де можуть сходитися/розходитися ''[[#Р|ребра]]'' та/або ''[[#Д|дуги]]''. [[Множина]] вершин графа G позначається V(G)
* '''Висяча вершина'''&nbsp;— ''[[Вершина (теорія графів)|вершина]]'', ''[[#С|степінь]]'' якої дорівнює 1 (тобто <math>d(v)=1</math>)
* '''Вага ребра'''&nbsp;— значення, [[Функція (математика)|поставлено у відповідність]] даному ''[[#Р|ребру]]'' ''[[#З|зваженого графа]]''. Зазвичай вага&nbsp;— [[Дійсні числа|дійсне число]], в такому випадку його можна [[Інтерпретація|інтерпретувати]] як «[[Міра множини|довжину]]» ребра.
* '''Відстань''' між двома вершинами графа&nbsp;— найменша довжина ''[[#Ш|шлях]]у'', що з'єднує ці вершини.
* '''[[Впорядкований граф]]'''&nbsp;— граф, в якому ребра, що виходять з кожної вершини, однозначно пронумеровані, починаючи з 1. Ребра вважаються впорядкованими в порядку зростання номерів. При графічному представленні часто ребра вважаються впорядкованими в порядку певного стандартного обходу (наприклад, проти годинникової стрілки).
* '''Вузол'''&nbsp;— те саме, що і ''[[Вершина (теорія графів)|Вершина]]''.

== Г ==
* '''[[Гамільтонів граф]]'''&nbsp;— граф, в якому є гамільтонів цикл.
* '''Гамільтонів шлях'''&nbsp;— ''[[#П|простий шлях]]'' в графі, що містить всі ''[[#В|вершини]]'' графа точно по одному разу.
* '''[[Гамільтонів цикл]]'''&nbsp;— ''[[#П|простий цикл]]'' в графі, що містить всі вершини графа точно по одному разу.
* '''[[Гармонійне розфарбування]]'''&nbsp;— це (правильне) розфарбування вершин, за якого будь-яка пара кольорів з'являється на суміжних вершинах не більше одного разу.
* '''Геометрична реалізація'''&nbsp;— фігура, вершинам якої відповідають вершини графа, ребрам&nbsp;— ребра графа, і ребра у фігурі поєднують вершини, що відповідають вершинам в графі.
* '''Геометричний граф'''&nbsp;— плоска фігура з вершин&nbsp;— точок площини і ребер&nbsp;— ліній, що з'єднують деякі пари вершин. Може зображати багатьма способами будь-який граф.
* '''[[Гіперграф]]'''&nbsp;— сукупність із множини вершин і множини гіперребер (підмножина n-го евклідового степеня множини вершин, тобто гіперребра об'єднують довільну кількість вершин).
* '''Гомеоморфні графи'''&nbsp;— графи, отримані з одного графа за допомогою послідовного підрозбиття ребер.
* '''[[Грань (теорія графів)|Грань]]'''&nbsp;— область, обмежена ребрами в ''[[#П|плоскому графі]]'', і така, що не містить всередині себе вершин і ребер графа. Зовнішня частина площини також утворює грань.
* '''[[Граф (математика)|Граф]]'''&nbsp;— базове поняття. Містить в собі множину ''[[#В|вершин]]'' і множину ''[[#Р|ребер]]'', що являє собою [[підмножина|підмножину]] [[Декартів добуток множин|декартового добутку]] множини вершин (тобто кожне ребро з'єднує рівно дві вершини).
* '''Граф роду''' g&nbsp;— граф, який можна зобразити без перетинань на [[рід поверхні|поверхні роду]] g і не можна зобразити без перетинань на жодній поверхні роду g-1.

== Д ==
* '''[[Двоїстий граф]]'''. Граф ''А'' називається двоїстим до планарного графа ''В'', якщо вершини графа ''А'' відповідають [[#Г|граням]] графа ''В'', і дві вершини графа ''A'' з'єднані ребром [[Тоді й лише тоді|тоді і тільки тоді]], коли відповідні грані графа ''B'' мають хоча б одне спільне ребро.
* '''[[Двочастковий граф]]''' або '''[[дводольний граф]]'''<ref>{{книга|автор=Ю. Нікольский, В. Пасічник, Ю. Щербина|назва=Дискретна математика|посилання=http://www.hyade.com.ua/index.php?option=com_content&view=article&id=2163:978-966-552-201-0&catid=44:development-all&Itemid=109|рік=2007|сторінки=368|isbn=978-966-552-201-0|місце=К|видавництво=BHV}}</ref> (або '''біграф''', або '''парний граф''')&nbsp;— граф <math>G(V,E)</math>, такий що множина вершин ''V'' розбита на дві підмножини <math>V_1</math> і <math>V_2</math>, що не перетинаються, при чому кожне ребро ''E'' інцидентне вершині з <math>V_1</math> і вершині з <math>V_2</math> (тобто з'єднує вершину з <math>V_1</math> з вершиною з <math>V_2</math>). Тобто, існує ''[[#П|правильне разфарбування графа]]'' двома кольорами. Множини <math>V_1</math> і <math>V_2</math> називають «долями» двочасткового графа. Двочастковий граф називается «повним», якщо будь-які дві вершини з <math>V_1</math> і <math>V_2</math> виявляться суміжними. Якщо <math>\left|V_1\right| = a</math>, <math>\left|V_2\right| = b</math>, то повний двочастковий граф позначається <math>K_{a,b}</math>.
* '''[[Деревний кістяк]]'''&nbsp;— [[Кістякове дерево|кістякове піддерево]] <math>T</math> графа <math>G</math>, в якому відстань між будь-якою парою вершин не перевищує <math>k</math>-разової [[Відстань (теорія графів)|відстані]] між ними у графі <math>G</math>.
* '''[[Дерево (теорія графів)|Дерево]]'''&nbsp;— ''[[#З|зв'язний граф]]'', що не містить ''[[#Ц|циклів]]''.
* '''[[Відстань (теорія графів)#Пов'язані поняття|Діаметр графа]]'''&nbsp;— максимальна відстань між вершинами для всіх пар вершин. Відстань між вершинами&nbsp;— найменша кількість ребер ''[[#Ш|шляху]]'', що з'єднує дві вершини.
* '''Довжина''' ''[[#М|маршрута]]''&nbsp;— кількість ребер в маршруті (з повтореннями). Якщо маршрут <math>M=v_0,e_1,v_1,e_2,v_2,...,e_k,v_k</math>, то довжина ''M'' дорівнює ''k'' (позначається <math>\left|M\right|=k</math>).
* '''Довжина''' ''[[#Ш|шляху]]''&nbsp;— кількість дуг шляху (або сума довжин його дуг, якщо останні задані). Так для шляху v<sub>1</sub>, v<sub>2</sub>, …, v<sub>n</sub> довжина дорівнює n-1.
* '''[[Доповнення графа]]'''&nbsp;— граф над тою самою множиною вершин, що і початковий, але вершини з'єднані ребрами тоді і тільки тоді, коли в початковому графі ребра немає.
* '''Дуга'''&nbsp;— орієнтоване ''[[#Р|ребро]]''.

== Е ==
* '''[[Евклідове мінімальне кістякове дерево]]'''
* '''Ейлерів граф'''&nbsp;— граф, в якому існує ''[[#Ц|цикл]]'', що містить усі ребра графа по одному разу, вершини можуть повторюватися.
* '''[[Ейлерів ланцюг]]''' (або '''[[Ейлерів цикл]]''')&nbsp;— ''[[Ланцюг (теорія графів)|ланцюг]]'' (''цикл''), що містить всі ребра графа, вершини можуть повторюватися.
* [[Екстремальна теорія графів]]
* '''{{якір2|Ексцентриситет вершини}}'''&nbsp;— максимальна ''[[#В|відстань]]'' від заданої вершини до будь-якої іншої.
* '''Елементарний шлях'''&nbsp;— ''[[#Ш|шлях]]'', вершини якого, за виключенням можливо, першої і останньої, різні. Іншими словами, простий шлях не проходить двічі через одну вершину, але може починатися і закінчуватися в тій самій вершині, в такому випадку він називається ''[[#Ц|циклом]]'' (елементарним циклом).
* '''Елементарним [[Стягування ребра|стягуванням]]''' називається така процедура: беремо ''[[#Р|ребро]]'' (разом інцидентними йому вершинами ''[[Вершина (теорія графів)|вершинами]]'', наприклад, u і v) і «стягуємо» його, тобто видаляємо ребро і ототожнюємо вершини u і v. Утворена вершина інцидентна ребрам, яким початково були інцидентні u або v крім видаленого.

== З ==
* {{якірець|зважений граф
}}'''Зважений граф'''&nbsp;— [[#Г|граф]], кожному ''[[#Р|ребру]]'' якого [[Функція (математика)|поставлено у відповідність]] деяке значення (''[[#В|вага ребра]]''). <!--доповнити про [[Алгоритм Дейкстри]]-->
* '''Зв'язність'''. Дві вершини в графі '''зв'язні''', якщо існує (простий) ''[[Ланцюг (теорія графів)|ланцюг]]'', що їх з'єднує.
* '''[[Зв'язний граф]]'''&nbsp;— граф, в якому всі вершини зв'язані.
* '''Граф-зірка'''&nbsp;— повний [[двочастковий граф]] <math>K_{1,b}</math>.
* '''[[Змішаний граф]]'''&nbsp;— граф, що містить як орієнтовані, так і неорієнтовані ''[[#Р|ребра]]''.

== І ==
* '''Ізольована вершина'''&nbsp;— вершина, ''[[#С|степінь]]'' якої дорівнює 0 (тобто не існують ребра ''інцидентні'' до неї).
* '''[[Ізоморфізм графів|Ізоморфізм]]'''. Два графи називаються '''ізоморфними''', якщо існує [[перестановка]] вершин, при якій вони збігаються. Іншими словами, два графи називаються '''ізоморфними''', якщо існує взаємооднозначна відповідність між їх вершинами і ребрами, така що зберігається ''суміжність'' та ''інцидентність''.
* '''[[Індекс доступності вершини]]''' (K)&nbsp;— K<sub>i</sub> = (ΣL)<sub>i</sub> / (ΣL)<sub>min</sub>, де ΣL&nbsp;— сума найкоротших віддалей вершини.
* '''Інтервальний граф'''&nbsp;— граф, вершини якого можуть бути поставлені у відповідність відрізкам на дійсній осі таким чином, що дві вершини інцидентні одному ребру тоді і тільки тоді, коли відрізки, що відповідають цим вершинам, перетинаються.
* '''[[Геометрія інцидентності|Інцидентність]]'''&nbsp;— поняття, що використовується тільки для ребра і вершини: якщо <math>v_1, v_2</math>&nbsp;— вершини, а <math>e=(v_1,v_2)</math>&nbsp;— ребро, що їх з'єднує, тоді вершина <math>v_1</math> і ребро ''e'' інцидентні, вершина <math>v_2</math> і ребро ''e'' також інцидентні. Дві вершини (або два ребра) інцидентними бути не можуть. Для позначення найближчих вершин (ребер) використовується поняття ''[[#С|суміжності]]''.

== К ==
* '''Каркасний підграф'''&nbsp;— підграф, що містить всі вершини{{Джерело?}}.
* '''[[Кінець (теорія графів)|Кінець]]''' нескінченного графа, це клас еквівалентності променів, в якому два промені еквівалентні, якщо існує третій промінь, який містить нескінченно багато вершин цих графів.
* '''[[Кістякове дерево|Кістякове (каркасне) дерево]]''' зв'язного графа G=(V, E) це таке [[Дерево (теорія графів)|дерево]] T=(V, E<sub>T</sub>), що E<sub>T</sub> ⊆ E<ref name="Трохимчук">{{книга|автор=Р.М.&nbsp;Трохимчук|назва=Теорія графів|посилання=http://irbis-nbuv.gov.ua/cgi-bin/irbis_nbuv/cgiirbis_64.exe?Z21ID=&I21DBN=EC&P21DBN=EC&S21STN=1&S21REF=10&S21FMT=fullw&C21COM=S&S21CNR=20&S21P01=3&S21P02=0&S21P03=A=&S21COLORTERMS=0&S21STR=Трохимчук%2C%20Ростислав%20Миколайович|видання=Навчальний посібник для студентів факультету кібернетики|рік=1998|сторінки=24|isbn=966-594-043-0|місце=К|видавництво=РВЦ «Київський університет»}}</ref>.
* '''Кістяковим (каркасним) лісом''' незв'язного графа G=(V, E) називають сукупність ''кістякових (каркасних) [[Дерево (теорія графів)|дерев]]'' ''компонент зв'язності графа'' G<ref name="Трохимчук" />.
* '''[[Кліка (теорія графів)|Кліка]]'''&nbsp;— підмножина вершин графа, повністю з'єднаних кожна з кожною, тобто підграф, що являє собою ''[[#П|повний граф]]''.
** '''[[Клікова ширина]]'''&nbsp;— параметр, який описує структурну складність графа.
** '''Клікове дерево'''&nbsp;— див. [[#Б|Блоковий граф]].
** '''Клікове число''' (''Clique number'')&nbsp;— число (G) вершин в найбільший кліці. ''Інші назви&nbsp;— густота, щільність.''
** '''Максимальна кліка'''&nbsp;— кліка з максимально можливою кількістю вершин графа.
* '''[[Клітка (теорія графів)|Клітка]]'''&nbsp;— ''[[регулярний граф]]'' найменшого ''[[Обхват (теорія графів)|обхвату]]'' для заданого степеня вершин.
* [[Коефіцієнт сітчастості]]&nbsp;— інваріант планарних графів.
* '''[[Компонента зв'язності графа]]'''&nbsp;— деяка підмножина ''[[Вершина (теорія графів)|вершин]]'' ''[[#Г|графа]]'' така, що для будь-яких двох вершин із цієї множини існує ''[[#Ш|шлях]]'' із однієї в іншу, і не існує шляху з вершини цієї множини в вершину не з цієї множини.
* '''[[Компонента сильної зв'язності графа]]''', '''шар'''&nbsp;— максимальна множина вершин [[#О|орієнтованого]] графа така, що для будь-яких двох вершин із цієї підмножини існує ''[[#Ш|шлях]]'' як із першої в другу, так і навпаки.
* '''Конструктивний перерахунок графів'''&nbsp;— отримання повного списку графів у заданому класі.
* '''Контур'''&nbsp;— ''[[#Ц|замкнений]]'' ''[[#Ш|шлях в орграфі]]''.
* '''[[Косе розбиття]]'''&nbsp;— [[Розбиття множини|розбиття]] вершин графа на дві підмножини у вигляді [[Зв'язний граф|незв'язного]] [[Породжений підграф|породженого підграфа]] та [[Доповнення графа|доповнення]].
* '''Коцикл'''&nbsp;— мінімальний ''[[#Р|розріз]]'', мінімальна множина ребер, видалення якої робить граф незв'язним.
* '''[[Кратні ребра]]'''&nbsp;— декілька ''[[#Р|ребер]]'', ''[[#И|інцидентних]]'' одній і тій самій парі вершин. Зустрічаються в ''[[#М|мультиграфах]]''.
* '''[[Кубічний граф]]'''&nbsp;— регулярний граф степеня 3, тобто граф, в якому кожній вершині інцидентні рівно три ребра.
* '''k-дольний граф'''&nbsp;— граф G, у якого ''[[хроматичне число]]'' c(G)=k

== Л ==
* '''[[Граф Ламана|Лама́нів граф]]''' з ''n'' вершинами&nbsp;— такий граф ''G'', що, по-перше, для кожного ''k'' будь-який підграф графа ''G'', що містить ''k'' вершин, має не більше, ніж 2''k''&nbsp;−3 ребра і, по-друге, граф ''G'' має рівно 2''n''&nbsp;−3 ребра.
* '''[[Лінійна деревність]]'''&nbsp;— найменша кількість лінійних лісів, на які можна розбити граф.
* '''[[Лінійний ліс]]'''&nbsp;— ліс, утворений з [[Диз'юнктне об'єднання|диз'юнктного об'єднання]] [[Шлях (теорія графів)|шляхів]]
* '''Ліс'''&nbsp;— неорієнтований граф без циклів. ''[[#К|Компонентами зв'язності]]'' лісу є ''[[#Д|дерева]]''.
* '''[[Ланцюг (теорія графів)|Ланцюг]]''' в графі&nbsp;— ''[[#М|маршрут]]'', всі ребра якого різні. Якщо всі ''[[#В|вершини]]'' (а таким чином і ребра) різні, то такий ланцюг називається '''простим''' ('''елементарним'''). В ланцюзі <math>v_0, e_1, ... , e_k, v_k</math> вершини <math>v_0</math> і <math>v_k</math> називаються '''кінцями''' ланцюга. Ланцюг із кінцями ''u'' і ''v'' '''з'єднує''' вершини ''u'' і ''v''. Ланцюг, що з'єднує вершини ''u'' і ''v'' позначається <math>\left\langle u,v\right\rangle</math>. Для ''[[Орієнтований граф|орграфів]]'' ланцюг називається орланцюгом. В деяких джерелах '''простий ланцюг'''&nbsp;— ланцюг, ''[[#Р|ребра]]'' якого різні, що є слабкою умовою.

== М ==
* '''[[Маршрут (теорія графів)]]'''<ref>В різних джерелах надають різні визначення маршруту, шляху, ланцюга, їх простоти та елементарності.</ref> в графі&nbsp;— послідовність вершин і ребер <math>v_0, e_1, v_1, e_2, v_2, ... , e_k, v_k</math>, що чергуються, в якій будь-які два сусідні елемента ''[[#І|інцидентні]]''. Якщо <math>v_0=v_k</math>, то маршрут '''замкнений''', інакше '''відкритий'''.
* '''[[Матриця досяжності]]''' орграфа&nbsp;— матриця, що містить інформацію про існування шляхів між вершинами орграфа.
* '''[[Матриця інцидентності]]''' графа&nbsp;— матриця, значення елементів якої характеризуються інцидентністю відповідних вершин графа (по вертикалі) та його ребер (по горизонталі). Для неорієнтованого графа елемент приймає значення '''1''', якщо вершина і ребро, що відповідають йому, інцидентні. Для [[#О|орієнтованого]] графа елемент приймає значення '''1''', якщо інцидентна вершина є початок ребра, значення '''-1''', якщо кінець; в інших випадках (в тому числі і для ''[[#П|петель]]'') значенню елемента присвоюється '''0'''.
* '''[[Матриця суміжності]]''' графа&nbsp;— матриця, значення елементів якої характеризується суміжністю вершин графа. При цьому, значенню елемента матриці присвоюється кількість ребер, які з'єднують відповідні вершини (тобто які ''[[#І|інцидентні]]'' обом вершинам). ''[[#П|Петля]]'' вважається одразу двома з'єднаннями для вершини, тобто до значення елемента матриці в такому випадку треба додавати '''2'''.
* '''Мережа'''&nbsp;— в принципі, те саме що і ''[[#Г|граф]]'', хоча мережами зазвичай називають графи, [[#В|вершини]] яких визначеним способом позначені.
* '''[[Мінімальне кістякове дерево|Мінімальний каркас]]''' (або '''Каркас мінімальної ваги''', '''Мінімальне кістякове дерево''') графа&nbsp;— ациклічна множина ребер в зв'язному, зваженому і неорієнтованому графі, що з'єднує між собою всі вершини цього графа, при цьому сума ваг усіх ребер у ньому мінімальна.
* '''[[Міст (теорія графів)|Міст]]'''&nbsp;— ребро, видалення якої збільшує кількість [[#К|компонент зв'язності]]. Рівнозначне визначення, ребро є мостом тоді і тільки тоді, коли вони не є частиною будь-якого [[#Ц|циклу]].
* '''Множина домінування'''&nbsp;— така множина вершин графа, що кожна вершина графа або належить їй, або суміжна деякій вершині, що належить множині домінування.
* '''Множина суміжності''' вершини ''v''&nbsp;— множина вершин, суміжних із вершиною ''v''. Позначається <math>\Gamma^+(v)</math>
* '''[[Мультиграф]]'''&nbsp;— граф, в якому існує пара вершин, що з'єднана більш ніж одним ребром (ненаправленим), або більше ніж двома дугами протилежних напрямків.

== Н ==
* '''[[Граф найближчих сусідів]]'''
* '''[[Напівстепінь входу]]''' в ''[[Орієнтований граф|орграфі]]'' для вершини ''v''&nbsp;— кількість дуг, що входять в вершину. Позначається <math>d^+(v)</math>.
* '''[[Напівстепінь виходу]]''' в ''[[Орієнтований граф|орграфі]]'' для вершини ''v''&nbsp;— кількість дуг, що виходять з вершини. Позначається <math>d^-(v)</math>.
* '''Направлений граф'''&nbsp;— [[орієнтований граф]], в якому дві вершини з'єднуються не більше ніж однією дугою.
** '''[[Направлений ациклічний граф]]'''&nbsp;— орієнтований граф без ''[[#К|контурів]]''.
* '''Незалежна множина вершин'''&nbsp;— (відома також як '''внутрішня стала множина''') множина вершин графа G, така, що будь-які дві вершини в ній не суміжні (жодна пара вершин не з'єднана ребром).
** Незалежна множина називається '''максимальною по включенню''', коли немає іншої незалежної множини, в яку вона б входила.
** '''[[Найбільша незалежна множина|Максимальною незалежною множиною]]''' називається незалежна множина з найбільшою кількістю вершин. Іншими словами, якщо Q це сім'я всіх незалежних множин графа G, то число a(G) = max |S| (де S належить Q) називається '''числом незалежності графа''' G, а множина S*, на якій цей максимум досягається, називається '''найбільшою незалежною множиною''' або '''максимальною незалежною множиною'''.
* '''Незалежна множина ребер'''&nbsp;— множина ребер графа G, така, що будь-які два ребра в ній не суміжні (жодна пара ребер не має спільної вершини).
* '''Нескінченний граф'''&nbsp;— це граф, який не є скінченним: він має нескінченно багато вершин, нескінченно багато ребер або те й інше разом. Див. також [[#С|Скінченний граф]].
* '''Нормований граф'''&nbsp;— ''[[#О|орієнтований граф]]'' без ''[[#Ц|циклів]].<!-- це точно не дубль? -->
* '''Нуль-граф''' ('''цілком незв'язний граф''', '''порожній граф''')&nbsp;— [[#Р|регулярний граф]] степеня 0, тобто граф, що не містить [[#Р|ребер]].

== О ==
* '''Обхват'''&nbsp;— довжина найменшого ''[[#Ц|циклу]]'' в графі.
* '''[[Ожина (теорія графів)|Ожина]]'''&nbsp;— для неорієнтованого графа G&nbsp;— сімейство зв'язних підграфів, які дотикаються один з одним: для будь-якої пари підграфів, які не мають спільних вершин, має існувати ребро, кінцеві вершини якого лежать у цих двох підграфах.
* '''Оточення'''&nbsp;— довжина найбільшого ''[[#П|простого циклу]] в графі.
* '''[[Орграф]]''', '''орієнтований граф''' G = (V, E) пара множин, в якій V&nbsp;— множина вершин (вузлів), E&nbsp;— множина дуг (орієнтованих ребер). Дуга&nbsp;— впорядкована пара вершин (v, w), в якій вершину v називають початком, а w&nbsp;— кінцем дуги. Можна сказати, що дуга v → w веде від вершини v до вершини w, при цьому вершина w суміжна з вершиною v.

== П ==
* '''Парний граф'''&nbsp;— те саме, що і ''[[двочастковий граф]]''.
* '''[[Петля (теорія графів)|Петля]]'''&nbsp;— ребро, початок і кінець якого знаходяться в одній і тій самій вершині.
* '''[[Перетин графів]]''' (позначених графів <math>G_1=(X_1, U_1)</math> і <math>G_2=(X_2, U_2)</math>)&nbsp;— граф <math>G_1 \cap G_2</math>, множина вершин якого є <math>X_1 \cap X_2</math>, а множина ребер&nbsp;— <math>U=U_1 \cap U_2</math>.
* '''[[Перерахунок графів]]'''&nbsp;— підрахунок числа неізоморфних графів в заданому класі (із заданими характеристиками).
* '''Переріз графа'''&nbsp;— множина ребер, видалення яких ділить граф на два ізольованих підграфи, один з яких, зокрема, може бути тривіальним графом.
* '''[[Граф перестановки]]'''&nbsp;— граф, вершини якого відповідають елементам перестановки, а ребра представляють пари елементів, порядок слідування яких змінився після перестановки.
* '''Периферійна вершина'''&nbsp;— це вершина з максимальним ексцентриситетом. У дереві це мусить бути лист.
* '''[[Підграф]]''' початкового графа&nbsp;— граф, що містить деяку підмножину вершин даного графа і всі ребра, ''[[#І|інцидентні]]'' даній підмножині.
* '''[[Планарний граф]]'''&nbsp;— граф, що може бути намальований (''[[#У|укладений]]'') на площині без перетину ребер. ''[[#І|Ізоморфний]]'' плоскому графу, тобто, є графом із перетинами, але таким, що допускає плоску укладку, через це може відрізнятися від ''плоского графа'' зображенням на площині. Таким чином, зображення на площині плоского і планарного графів можуть відрізнятись.
* '''[[Плоский граф]]'''&nbsp;— ''[[#Г|геометричний граф]]'', в якому жодні два ребра не мають спільних точок крім інцидентним їм обом вершинам (не перетинаються). Є ''[[#У|укладеним]]'' графом на площині.
* '''[[Повне розфарбування]]'''
* '''[[Повний граф|Повним графом]]''' називається граф, в якому для кожної пари вершин <math>v_1, v_2</math>, існує ребро, інцидентне <math>v_1</math> і інцидентне <math>v_2</math> (кожна вершина з'єднана ребром з будь-якою іншою вершиною).
* '''Повним двочастковим''' називається ''[[двочастковий граф]]'', в якому кожна вершина одної підмножини з'єднана ребром з кожною вершиною іншої підмножини.
* '''[[Породжений підграф]]'''&nbsp;— підграф, породжений множиною вершин похідного графа.
* '''Порожній граф'''&nbsp;— див. ''[[#Н|нуль-граф]]''.
* '''[[Потужність графа]]'''&nbsp;— найменше відношення кількості ребер, видалених із графа, до числа компонент, отриманих внаслідок такого видалення (зменшеного на 1).
* '''[[Правильне розфарбування графа]]'''&nbsp;— ''[[Розфарбовування графів|розфарбування]]'', при якому кожний кольоровий клас є незалежною множиною. Інакше кажучи, в правильному [[Розфарбовування графів|розфарбуванні]] будь-які дві суміжні вершини повинні мати різні кольори.
* '''Простий ланцюг'''&nbsp;— ''маршрут'', в якому всі вершини різні.
* '''[[Простий граф]]'''&nbsp;— ''граф'', в якому немає ''[[#К|кратних ребер]]'' і ''петель''.
** '''Простий цикл'''&nbsp;— ''[[#Ц|цикл]]'', що не проходить двічі через одну вершину.
* '''[[Псевдограф]]'''&nbsp;— граф, що містить ''петлі''.
* '''[[Псевдоліс]]'''&nbsp;— [[Граф (математика)|неорієнтований граф]], у якому будь-яка [[Компонента зв'язності графа|зв'язна компонента]] має не більше одного [[Цикл (теорія графів)|циклу]].

== Р ==
* '''[[Відстань (теорія графів)#Пов'язані поняття|Радіус графа]]'''&nbsp;— мінімальний з ''[[Відстань (теорія графів)#Пов'язані поняття|ексцентриситетів]]'' вершин зв'язаного графа; вершина, на якій досягається цей мінімум називається центральною вершиною.
* '''Ребро графа''' (дуга графа)&nbsp;— базове поняття. Ребро з'єднує дві ''[[Вершина (теорія графів)|вершини]]'' графа.
* '''[[Регулярний граф]]'''&nbsp;— граф, ''[[Степінь вершини|степені]]'' всіх вершин якого рівні. Степінь регулярності є [[Інваріант (математика)|інваріантом]] графа і позначається <math>r(G)</math>. Для нерегулярних графів <math>r(G)</math> не визначено. Регулярні графи являють собою особливу складність для багатьох алгоритмів.
** '''Регулярний граф степеня 0''' ('''цілком незв'язний граф''', '''порожній граф''', '''нуль-граф''')&nbsp;— граф без [[#Р|ребер]].
* '''[[Резистивна відстань]]'''
* '''[[Розгортка графа]]'''&nbsp;— функція, що задана на вершинах орієнтовного графа.
* '''[[Розмітка графа|Розмічений граф]]'''&nbsp;— граф, для якого задана множина позначок S, функція розмітки вершин f: A → S і функція розмітки дуг g: R → S. Графічно ці функції представляються надписуванням позначок на вершинах і дугах. Множина позначок може поділятися на дві підмножини позначок вершин і дуг, що не перетинаються.
* '''Розріз'''&nbsp;— множина ''ребер'', видалення якої робить граф [[#З|незв'язним]].
* '''[[Хроматичне число|Розфарбування графа]]'''&nbsp;— розбиття вершин на множини, що називаються пелюстками. Якщо при цьому немає двох суміжних вершин, що належать до одної множини (тобто всі суміжні вершини завжди різного кольору), то таке розфарбування називається правильним.

== С ==
* '''[[Самодвоїстий граф]]'''&nbsp;— граф, ''[[#І|ізоморфний]]'' своєму ''[[#Д|двоїстому графу]]''.
* '''Сильна зв'язність'''. Дві вершини в ''[[Орієнтований граф|орграфі]]'' '''сильно зв'язані''', якщо існує шлях з однієї в другу і назад.
** '''Сильно зв'язаний орграф'''&nbsp;— ''орграф'', в якому всі вершини сильно зв'язані.
* '''[[Сильно регулярний граф]]'''
* '''Скінченний граф'''&nbsp;— граф, який має скінченне число вершин і скінченну кількість ребер. Багато джерел припускають, що всі графи скінченні, явно не кажучи про це. Граф є '''локально скінченним''', якщо кожна вершина має скінченне число інцидентних ребер. Див. також [[#Н|Нескінченний граф]].
* '''[[Спектральна теорія графів|Спектр графа]]'''&nbsp;— множина всіх власних значень матриці суміжності з урахуванням кратних ребер.
* '''[[Степінь вершини (теорія графів)|Степінь вершини]]'''&nbsp;— кількість ребер графа ''G'', що ''[[#І|інцидентні]]'' вершині ''x''. Позначається <math>d(x)</math>. ''Мінімальний'' степінь вершини графа ''G'' позначається <math>\delta(G)</math>. а ''максимальний''&nbsp;— <math>\Delta(G)</math>.
* '''[[Стягування ребра]]''' графа&nbsp;— заміна кінців ребра однією вершиною, сусідами нової вершини стають сусіди цих кінців. Граф <math>G_1</math> '''можна стягнути''' до <math>G_2</math>, якщо другий можна отримати послідовним стягуванням ребер першого.
* '''Суграф''' ('''частковий граф''') початкового графа&nbsp;— граф, що містить всі вершини початкового графа і підмножину його ''[[#Р|ребер]]''.
* '''[[Сума за клікою]]'''&nbsp;— операція, що забезпечує комбінацію двох графів склеюванням їх за клікою, подібно до зв'язної суми в топології.
* '''Суміжність'''&nbsp;— поняття, яке використовується по відношенню тільки до двох ''[[#Р|ребер]]'' або двох ''[[#В|вершин]]'': Два ребра, ''[[#І|інцидентні]]'' одній вершині, називаються '''суміжними'''; дві вершини, ''інцидентні'' одному ребру, також називаються суміжними.

== Т ==
* {{якір|граф тета}}'''Тета'''&nbsp;— граф, що складається з об'єднання трьох шляхів, які не мають усередині спільних вершин, у яких кінцеві вершини одні й ті ж<ref>
{{книга
|автор=J. A. Bondy
|вклад=The "graph theory" of the Greek alphabet
|doi = 10.1007/BFb0067356
|mr = 0335362
|страницы= 43–54
|издательство=Springer
|серия=Lecture Notes in Mathematics
|заголовок=Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs)
|том=303
|год=1972
}}</ref>
* '''[[Тета-граф]]'''&nbsp;— вид [[геометричний кістяк|геометричного кістяка]].
* '''[[Товщина графа]]'''
* '''Тривіальний граф'''&nbsp;— граф, що складається з однієї ''[[#В|вершини]]''.
* '''[[Тріангуляція поверхні]]'''&nbsp;— ''[[#У|укладка]]'' графа на [[поверхня|поверхню]], яка розбиває її на трикутні області; окремий випадок [[Тріангуляція (геометрія)|триангуляції]].
* '''[[Тотожний граф]]'''&nbsp;— граф, у якого можливий лише один єдиний ''[[#А|автоморфізм]]''&nbsp;— тотожний. Образно кажучи, тотожний граф&nbsp;— «абсолютно несиметричний» граф.
* '''[[Т-розфарбування]]'''
* '''[[Турнір (теорія графів)|Турнір]]'''&nbsp;— ''[[#О|орієнтований граф]]'', в якому кожна пара вершин з'єднана одним ребром.

== У ==
* '''[[Вкладення графу|Укладення]]''': граф укладається на поверхню, якщо його можливо намалювати на цій поверхні так, щоб ''[[#Р|ребра]]'' графа при цьому не перетинались. (Див. [[#П|''Планарний граф'', ''Плоский граф'']].)

== Ф ==
* '''n-фактор''' графа&nbsp;— регулярний [[Кістякове дерево|кістяковий підграф]] ступені <math>n</math>.
* '''[[Факторизація графа|n-факторизація]]''' графа&nbsp;— розбиття графа на незалежні ''n-фактори''.
* '''[[Фактор-граф]]'''

== Х ==
* '''[[Хроматичне число]]''' графа&nbsp;— мінімальна кількість кольорів, що необхідна для ''[[Розфарбовування графів|розфарбування]]'' вершин графа, при якому будь-які суміжні вершини розфарбовані в різні кольори.
* '''[[Хроматичний індекс]]''' графа&nbsp;— мінімальна кількість кольорів, що необхідна для ''[[Розфарбовування графів|розфарбування]]'' ребер графа, при якому будь-які суміжні ребра розфарбовані в різні кольори.

== Ц ==
* '''[[Центр графа]]'''&nbsp;— множина всіх вершин з найменшим [[#Ексцентриситет вершини|ексцентриситетом]].
* '''[[Цикл (теорія графів)|Цикл]]'''&nbsp;— замкнений ''[[Ланцюг (теорія графів)|ланцюг]]''. Для ''орграфів'' цикл називають ''контуром''.
** '''Цикл''' ('''простий цикл''') в ''[[Орієнтований граф|орграфі]]''&nbsp;— ''[[#П|простий шлях]]'' ''[[#Д|довжини]]'' не менш ніж 1, який починається і закінчується в одній і тій самій вершині.
** '''Цикл Гамільтона'''&nbsp;— те саме, що і ''[[#Г|Гамільтонів цикл]]''.
* '''[[Цикломатичне число]] графа'''&nbsp;— число ''[[#К|компонент зв'язності]]'' графа плюс число ''[[#Р|ребер]]'' мінус число ''[[#В|вершин]]''.
* '''Цілком незв'язний граф''' ('''пустий граф''', '''нуль-граф''')&nbsp;— [[#Р|регулярний граф]] степеня 0, тобто граф без [[#Р|ребер]].

== Ч ==
* '''Частковий граф'''&nbsp;— те саме, що ''[[#С|субграф]] та [[Кістякове дерево|кістяковий підграф]]''.
* '''Число домінування'''&nbsp;— найменша потужність [[#М|множини домінування]] у графі.
* '''[[Число незалежності]]''' або '''число внутрішньої сті́йкості''' графа&nbsp;— це розмір найбільшої [[Задача про незалежну множину|незалежної множини вершин]] у ньому.

== Ш ==
* '''[[Шлях (теорія графів)|Шлях]]'''&nbsp;— див. ''[[#М|маршрут]]''. Шлях, в якому будь-яка вершина не зустрічається двічі, називається елементарним.
* '''Шлях в орграфі'''&nbsp;— послідовність вершин v<sub>1</sub>, v<sub>2</sub>, …, v<sub>n</sub>, для якої існують дуги v<sub>1</sub> → v<sub>2</sub>, v<sub>2</sub> → v<sub>3</sub>, …, v<sub>n-1</sub> → v<sub>n</sub>. Кажуть, що шлях починається у вершині v<sub>1</sub>, проходить через вершини v<sub>2</sub>, v<sub>3</sub>, …, v<sub>n-1</sub>, і закінчується у вершині v<sub>n</sub>.

== Я ==
* '''[[Граф Яо]]'''&nbsp;— вид [[геометричний кістяк|геометричного кістяка]].

{{Індекс категорії АБВ (зручний)}}

== Примітки ==
{{reflist}}

== Посилання ==
* Chris Caldwell [http://www.utm.edu/departments/math/graph/glossary.html Graph Theory Glossary]

{{термінологія}}

[[Категорія:Теорія графів|*]]
[[Категорія:Термінологічні словники у Вікіпедії|Теорія графів]]