7. Графи

Приклади розв’язання типових задач

Задача 1. Нехай – зв’язний граф і– деяке його ребро. Позначимо черезграф, який отримано звилученням ребра. Довести, що:

1. граф є зв’язним, якщо реброналежить циклу в графі;

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

Розв’язання.

a) Нехай дві довільні вершини іє зв’язаними у графі. Покажемо, що вони будуть зв’язаними і у. Можливі два випадки. Якщо маршрут, що з’єднуєіу зв’язному графі , не містить ребро, то вилучення цього ребра не змінить зв’язностііу графі. Якщо ж реброналежить маршрутуі, то маршрут, що веде зуу графі, можна побудувати таким чином:

• беремо маршрут, що веде з в;

• додаємо до нього ту частину циклу, що містив ребро , яка залишилась у графіта з’єднуємо вершиниі;

• беремо маршрут, що веде з в.

Отже, побудовано “обхідний” маршрут з до. Тому графє зв’язним.

b) Нехай ребро не належить жодному циклу графа. Тоді у графівершинитабудуть незв’язаними і будуть належати двом різним компонентам зв’язностітаграфа. Крім того, у графістануть незв’язаними ті і тільки ті вершини, які були з’єднані у графімаршрутом, що містив ребро. Отже, кожна вершинаубуде зв’язаною або з вершиною, або з вершиною, тобтоналежатиме або, або. Це і означає, щомає рівно дві компоненти зв’язності.

Задача 2. Якщо у простому графі тільки дві вершинитамають непарні степені, то вони зв’язані. Довести.

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

Задача 3. Довести, що графи таізоморфні.

3

4

Розв’язання. Побудуємо бієктивне відображення , що зберігає суміжність вершин в графахта:

.

При побудові відображення враховуємо степінь вершин графів: в графі існує одна вершина степені 4:. У графітеж існує лише одна вершинастепені 4, отже, . У графі вершина 1 суміжна з вершинами 2 та 5, які мають степінь 2. У графіїм відповідають вершинита, отже, можна покласти та , і т.д.

Потрібно перевірити, що побудоване відображення дійсно зберігає суміжність вершин. Випишемо множину ребер графа:

.

Побудуємо множину :

.

Очевидно, що , тобто, якщо вершинитає суміжними у графі, то їх образитає суміжними у графі. Отже, графитаізоморфні.

Зауважимо, що відображення можна побудувати не єдиним чином. Наприклад,. Легко перевірити, що це відображення також зберігає суміжність вершин.

Задача 4. Нехай – ациклічний граф,і. Довести, що графє деревом.

Розв’язання. Дерево – це зв’язний ациклічний граф. Отже, потрібно довести, що – це зв’язний граф. Доведення проведемо від супротивного. Нехай– незв’язний граф, який маєкомпонент зв’язності:, причому. Тоді кожен з графівє деревом. Нехай. Тоді. Просумувавши по всіх значеннях, маємо:або . Врахувавши, що за умовою , маємо. Отримали протиріччя припущенню. Отже, графмає лише одну компоненту зв’язності, тобто є зв’язним. Це і означає, що граф Е є деревом.

A7

1. Побудувати діаграму, матрицю суміжності та інцидентності графа , де , .

2. Нехай задано матрицю суміжності деякого графа . Як за допомогою матрицівизначити:

1. кількість вершин графа ;

2. кількість ребер графа ;

3. степінь певної вершиниграфа;

4. чи має граф петлі;

5. чи є повним графом.

3. Побудувати діаграму повного графа з вершинами для:

а) ;b) ;c) ;d) ;e) ;f) .

4. Скільки ребер має повний граф з вершинами?

5. Побудувати декілька підграфів графа та декілька його остовних підграфів.

6. Скільки ребер у графі з вершинами, якщо кожна його вершина має степінь 2?

7. Чи існує граф із вершинами, усі вершини якого є кінцевими, якщо:

a) ; b) ?

8. Побудувати доповнення наведених графів:

a)

9. У певному товаристві з осіб кожен знайомий зі тількиіншими особами. Чи можливе таке товариство для:

a) ; b) ; c) ; d) ?

10. Нехай графи ізадано за допомогою матриць суміжностіівідповідно,. Визначити матрицю суміжностідля графа:

a) ;b) ;c) ;d) .

11. Чому дорівнює степінь вершини у графі, якщо у графізвершинами:

a) ;b) ;c) ;d) ?

12. Нехай задано граф :

4

2

5

1

Чи буде послідовність вершин 1 2 1 5 2 4 маршрутом? Побудувати:

1. маршрут, який з’єднує вершини 1 та 4 і не є ланцюгом;

2. ланцюг, який з’єднує вершини 1 та 4 і не є простим ланцюгом;

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

4. циклічний маршрут, який містить вершину 1 та не є циклом;

5. цикл, який містить вершину 1 та не є простим циклом;

6. прості цикли, які містять вершину 1 та мають найбільшу та найменшу довжини.

13. Нехай задано граф :

1

3

4

8

9

Знайти всі ланцюги, які з’єднують вершини 1 та 9. Скільки серед них буде простих?

14. Довести, що граф ізоморфний графута графізоморфний графу. Показати, що графізоморфний графу.

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

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

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

18. Побудувати всі дерева з п’ятьма вершинами (з точністю до ізоморфізму).

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

20. Довести, що будь-яке дерево з вершинами () має принаймні дві кінцеві вершини.

21. Для графів тапобудувати відповідні їм остовні дерева:

1. вилучаючи ребро з кожного циклу;

2. пошуком в ширину;

3. пошуком в глибину.

22. Скільки ребер потрібно вилучити зі зв’язного графа звершинами таребрами, щоб отримати остовне дерево?

23. Нехай граф задано за допомогою матриці суміжності. Побудувати діаграму графата його матрицю інцидентності, якщо

.

Знайти напівстепені входу і виходу кожної вершини. Зясувати, чи має цей граф джерело та стік.

24. Побудувати орієнтований граф з сімома вершинами, який має 2 недосяжні і 3 тупикові вершини.

B7

1. Побудувати діаграму, матрицю суміжності та інцидентності графа де , .

2. Нехай граф задано за допомогою матриці суміжності, граф– за допомогою матриці інцидентності. Побудувати діаграми цих графів, якщо

.

3. Побудувати всі графи з чотирма вершинами і ребрами

4. Чи існує повний граф, у якого кількість ребер дорівнює:

1. 15; b) 18; c) ?

5. Чи існує граф із шістьма вершинами, степені яких дорівнюють:

1. 1, 2, 3, 3, 4, 4; b) 2, 3, 3, 4, 4, 4; c) 2, 2, 2, 4, 5, 5.

Відповідь обґрунтувати.

6. Побудувати граф із п’ятьма вершинами, у якому тільки дві вершини мають однакові степені. Чи можуть ці вершини мати степінь 0 або степінь 4?

7. Побудувати об’єднання, перетин, різницю та доповнення графів:

8. Нехай задано два графи та:

Вилучити з графа :

a) вершину ; b) вершину ;c) ребро .

Вилучити з графа вершину.

9. Нехай задано граф :

1. Вказати степінь кожної вершини.

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

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

4. Чому дорівнюватимуть степені вершин 3 та 5 у графі ?

9. Нехай у графі з вершинами і ребрами євершин степеня, а всі інші вершини мають степінь. Довести, що.

10. Кубічний граф – це граф, степінь кожної вершини якого дорівнює 3. Побудувати кубічний граф, що має:

1. 4 вершини; b) 6 вершин; c) 8 вершин.

Чи існує кубічний граф з вершинами, якщо:

а) b) ?

9. Скільки вершин повинен мати кубічний граф? Скільки ребер у такому графі?

10. Довести, що доповнення кубічного графа не є кубічним графом.

11. Чому дорівнює кількість ребер у графі , якщо графмаєвершин іребер?

12. Чи існує самодоповнювальний граф, у якого кількість ребер дорівнює: a) ;b) ?

13. Побудувати всі самодоповнювальні графи із п’ятьма вершинами.

14. Нехай задано граф :

Які з наведених нижче послідовностей вершин є маршрутом:

a) ; b) ; c) ; d) ?

Вказати ланцюги, прості ланцюги та довжину кожного маршруту.

9. Чи має граф

1. маршрут довжиною 5;

2. ланцюг довжиною 5;

3. простий ланцюг довжиною 5.

Навести приклади.

9. Якщо два різні цикли графа містять ребро, то в графііснує цикл, серед ребер якого немає ребра. Довести.

10. Побудувати всі дерева з 6 вершинами (з точністю до ізоморфізму).

11. Довести, що в дереві звершинами виконується рівність, дестепінь вершини.

12. Яку найбільшу і найменшу кількості кінцевих вершин може мати дерево з вершинами? Яку структуру мають такі дерева?

13. Описати всі дерева, доповнення яких також є деревами.

14. Описати всі дерева, які є самодоповнювальними графами.

15. Скільки основних дерев має повний граф ?

16. Побудувати орієнтований граф, який має 8 вершин, 2 стоки та одне джерело.

17. Побудувати повний орієнтований граф з шістьма вершинами.

C7

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

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

3. Довести, що якщо зі зв’язного графа видалити довільне ребро, що міститься в деякому простому циклі, то граф залишиться зв’язним.

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

5. Задача Рамсея. Довести, що серед довільних шести осіб знайдуться або троє попарно знайомих, або троє попарно незнайомих.

6. З’ясувати, чи будуть ізоморфними графи:

a)

b)

4

c)

4

d)

9. Довести, що в графі з вершинами, який має більше ніжребро, є принаймні один цикл.

10. Описати у термінах теорії графів наступні бінарні відношення на скінченній множині: a) транзитивні відношення; b) відношення еквівалентності; c) відношення часткового порядку; d) відношення лінійного порядку.

11. Описати відношення, що відповідають: a) орієнтованим графам без петель; b) неорієнтованим графам без петель; c) орієнтованим графам з петлями.