Лекція №18. Структури та параметри графів

Кліки

Діаметр, обхват та оточення графа

Відстані між вершинами

Ступені графа

Означення 18.1 Кліка – це повний підграф.

Означення 18.2 Доповнення графа має множину вершин . Дві вершини в суміжні тоді і тільки тоді, коли вони не суміжні в .

Наприклад:

Означення 18.3 Самодоповнюючийся граф - це граф, який ізоморфний своєму доповненню.

Наприклад:

Означення 18.4 Відстанню між двома вершинами і графа називається довжина найкоротшого простого ланцюга, який з’єднує ці вершини.

Якщо і не з’єднані, то .

В зв’язному графі відстань являється метрикою і задовольняє аксіомам метрики. Для будь-яких трьох вершин виконуються умови:

тоді і тільки тоді, коли .

Найкоротший простий ланцюг часто називають геодезичною.

Діаметр зв’язного графа - це довжина самої довгої геодезичної.

Обхват графа - це довжина найкоротшого простого циклу графа , якщо він є.

Оточення - це довжина самого довгого простого циклу графа .

Наприклад:

	Обхват: Оточення: Діаметр:

Квадрат графа має ту саму множину вершин, що і граф , тобто і дві вершини і в суміжні тоді і тільки тоді, коли відстань в .

Ступені визначаються аналогічно.

Наприклад: Введемо позначення - простий цикл з вершинами, - простий ланцюг з вершинами, - повний граф.

Тоді

Питання для самоперевірки та вправи

1. Що таке кліка ? Намалюйте граф, який містить кліку.

2. Дайте означення відстані між двома вершинами графа, діаметра, обхвата, оточення графа.

3. Наведіть приклад самодоповнюючогося графа.

4. Довести, що будь-який самодоповнюючийся граф має або вершин.

Лекція №19. Мости, блоки

Означення точки сполучення, моста, блока.

Теорема про точку сполучення.

Теорема про мост графа.

Застосування теорем до обчислення графів.

Точкою сполучення графа називається вершина, вилучення якої збільшує число компонент зв’язності.

Ребро з такою властивістю називається мостом.

Таким чином, якщо - точка сполучення графа , то граф - незв’язний.

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

Блок графа – це його максимальний нероздільний підграф.

Якщо - нероздільний граф, то часто він сам називається блоком.

Вершина - точка сполучення. Вершина - не точка сполучення. - міст; - не міст.

Блоки графа :

Теорема 19.1 Нехай - вершина зв’язного графа. Наступні ствердження еквівалентні:

(1) - точка сполучення графа ;

(2) існують такі вершини і , що належить будь-якому простому

- ланцюгу;

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

Доведення:

: Оскільки - точка сполучення графа , то граф - незв’язний і має хоча б дві компоненти зв’язності.

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

: Це слідує з того, що - окремий випадок (3).

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

Теорема 19.2 Нехай - ребро зв’язного графа . Наступні ствердження еквівалентні:

(1) - міст графа ;

(2) не належить жодному простому циклу графа ;

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

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

Теорема 19.3 В будь-якому нетривіальному зв’язному графі знайдуться принаймні дві вершини, які не являються точками сполучення.

Доведення:

Нехай і - вершини графа , максимально віддалених одна від одної, тобто такі, що .

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

Отже, лежить на будь-якому - ланцюгу і тому , що неможливо. Отже, , а також не являються точками сполучення.