Гамільтонів цикл

Гамільтоновим циклом у зв’язному² неорієнтованому графі називають елементарний цикл (вершини не повторюються), який проходить через кожну вершину графа.

Граф, який має гамільтонів цикл, називається гамільтоновим.

Гамільтоновим ланцюгом (ще кажуть: гамільтоновим шляхом) у зв’язному неорієнтованому графі називають елементарний ланцюг (вершини не повторюються), який проходить через кожну вершину графа.

Гамільтонові цикл і ланцюг у загальному випадку не містять всіх ребер графа.

Приклад (задача Гамільтона). Чи можна, почавши з будь-якого міста, відвідати решту 19 міст, побувавши в кожному з них по одному разу, і повернутися назад в початкове місто, якщо схема доріг має вигляд:

Задачі дослідження наявності в графі гамільтонового циклу чи ланцюга на перший погляд досить близькі до задач знаходження ейлерового циклу чи ланцюга. Але насправді вони значно складніші. Критерій існування гамільтонового циклу ще не знайдений.

Необхідною умовою існування гамільтонового циклу є не менш ніж 2-зв’язність графа. Дослідження достатніх умов наявності в графові гамільтонового циклу є одним з важливих напрямів у теорії графів. Якщо граф має багато ребер і вони досить рівномірно розміщені, то з великою ймовірністю можна вважати, що такий граф має гамільтонів цикл. Наведена нижче теорема дає достатню умову існування гамільтонового циклу.

Теорема (Дірака, 1952). Якщо у зв’язному графі з кількістю вершин степінь кожної вершини не менший ніж , то цей граф має гамільтонів шлях.

У повному графі завжди існує гамільтонів ланцюг (це достатня умова).

Дводольні графи

Дводольним (ще кажуть: двобічним) називається граф, множину вершин V якого розбито на дві підмножини і , які не перетинаються ( , ), і ребра зв’язують вершини тільки з різних підмножин. На такому графі немає ребер, які з’єднують між собою вершини з тої самої множини.

Дводольний граф називається повним, якщо кожну вершину з з’єднано ребром з кожною вершиною з , Повний дводольний граф позначають , де і кількості елементів множин і відповідно. Граф має вершин і ребер. Граф називається зіркою.

Приклад. Нижче подано дводольні графи:

При цьому перші три графи , , є повними, а четвертий граф G неповний. Граф є зіркою.

Дводольним графом можна описати ряд задач про / пов’язаних . прикладом такої задачі є задача про призначення. Нехай є кілька різних вакансій і група осіб, які претендують на певні вакансії . При цьому кожен з претендентів має достатню кваліфікацію для кількох, але не всіх посад. Треба визначити, чи можна надати кожному із цих претендентів одну з тих посад, на яку від підходить.

Теорема (Кеніга). Для того, щоб граф був дводольним, необхідно й достатньо, щоб він не містив простих циклів з непарною довжиною (тобто граф є дводольним, тоді і тільки тоді, коли всі його цикли мають парну довжину).

Щоб розпізнати дводольність графа застосовують пошук вшир.

Алгоритм розпізнання дводольності графа. Довільній вершині графа G надамо номер 1. Кожній суміжній з цією вершиною вершині припишемо номер 2, а суміжним з ними — номер 3 і т.д. Якщо серед вершин з однаковими номерами немає суміжних, то граф дводольний. Наочно це можна перевірити, розбивши множину вершин на дві підмножини — з непарними номерами і — з парними номерами і побудувавши графи і : якщо ці графи не мають ребер, то граф G —дводольний.

Приклад. Розглянемо два графи і, відповідно до алгоритму розпізнавання дводольності, перенумеруємо вершини:

Оскільки в першому графі дві вершини з номером 3 з’єднані ребром, то цей граф не дводольний. У другому графі немає жодної пари вершин з різними номерами, які були б суміжними; отже, цей граф — дводольний.

Дерева

Деревом називається зв’язний граф без циклів, де . Такий граф не має ні петель, ні кратних ребер.

При видаленні будь-якого ребра дерево втрачає зв’язність і з нього утворюються два дерева.

Незв’язний граф, кожна компонента зв’язності якого є деревом, називається лісом.

Найпростіше дерево має дві вершини, з’єднані одним ребром. Якщо до дерева додати ще одне ребро, то разом з ним додасться й вершина. Отже, якщо дерево має n вершин, то воно має ( ) ребро.

Теорема. Щоб скінченний зв’язний граф був деревом, необхідно й достатньо, щоб кількість його ребер була на 1 меншою від кількості його вершин: .

Дана властивість може бути використана також як означення дерева.

Цикломатичне число дерева дорівнює нулю: .

Наслідок. Якщо ліс має n вершин і складається з k дерев, то кількість його ребер дорівнює ( ).

Дерева, як і будь-які графи, можуть бути орієнтованими й неорієнтованими.

У неорієнтованому дереві будь-які дві різні вершини з’єднані одним елементарним (вершини не повторюються) ланцюгом. Якщо будь-які дві вершини неорієнтованого дерева з’єднати ребром, то одержаний граф перестане бути деревом і він міститиме рівно один елементарний цикл.

Нехай граф має n вершин, m ребер, k компонент зв’язності і його цикломатичне число. Для неорієнтованих дерев рівносильні такі висловлювання.

1. , (за означенням).

2. , .

3. , .

4. Для будь-якої пари вершин існує один (і тільки один) ланцюг, який з’єднує ці вершини.

5. , але, якщо з дерева видалити будь-яке ребро, то для одержаного графа .

6. , але, якщо до дерева додати будь-яке ребро, не додаючи вершин, то для одержаного графа .

Теорема. Будь-яке дерево з кількістю вершин має принаймні дві висячі вершини.

Центр центроїд дерева

У неорієнтованому дереві можна виділити будь-яку одну вершину (позначимо її ), яку називають його коренем. Коренева вершина може мати будь-який степінь. Вершину із будь-якою висячою вершиною, яка називається кінцевою, можна з’єднати ланцюгом, який називається гілкою.

Нехай — неорієнтований граф з n вершинами і m ребрами.

Теорема Келлі. Кількість різних дерев, побудованих на n вершинах (з точністю до ізоморфності) дорівнює .