Задачі до теми „Графи”

Приклад 1. Довести, що графи на рис. 1 неізоморфні, а графи на рис. 2 (що мають по 7 вершин по периметру) ізоморфні.

Рис. 1. Рис. 2.

Приклад 2. Переконайтеся, що такі об’єкти можна розглядати як графи (орієнтовані графи):

а) вершини та ребра многогранника;

б) план лабіринту;

в) дружні відносити між людьми, які запрошені на вечірку;

г) стадії гри в хрестики-нулики;

д) футбольний турнір;

е) дільники заданого натурального числа;

є) країни на карті.

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

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

Приклад 5. Довести, що кількість ребер однорідного графа степеня r, який має n вершин, дорівнює nr/2.

Приклад 6. Для того, щоб у зв’язному графі існував ланцюг ab, який містить всі ребра лише один раз, необхідно і достатньо, щоб a і b були єдиними вершинами непарного степеня цього графа.

Приклад 7. Показати, що графи, зображені на рисунку, не ізоморфні.

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

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

Приклад 10. Торговець, який живе у місті A₁, збирається відвідати міста A₂, A₃, A₄. Відстані між містами такі: A₁A₂ = 120, A₁A₃ = 140, A₁A₄ = 180, A₂A₃ = 70, A₂A₄ = 100, A₃A₄ = 110. Знайти найкоротший циклічний шлях з A₁, який проходить через три інші міста.

Приклад 11. Скільки ходів конем можна зробити на шаховій дошці?

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

Приклад 13. Довести, що граф, який відповідає ходам коня на шаховій дошці, не є Ейлеровим.

Приклад 14. Скільки існує простих орієнтованих графів, які мають 5 вершин?

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

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

Приклад 17.Довести, що не існує графа, який має 24 вершини, з них 11 вершин степеня 7, 10 вершин степеня 5 і 3 вершини степеня 3.

Приклад 18. Нехай граф G_n має n вершин, які занумеровані натуральними числами 1, 2, ..., n. У графі G_n i-та та j-та вершини з’єднані ребром, якщо НСД(i, j) = 1. Записати матриці Кіркгофа, суміжності та інцидентності графів G₄, G₅, G₆. Чи є граф G_n зв’язним?

Приклад 19. Циклічним порядком зв’язного графа називають найменше число його ребер, які потрібно вилучити, щоб одержати дерево. Довести таке: коли граф має l ребер і n вершин, то його циклічний порядок дорівнює l – n + 1.

Приклад 20. Доведіть, що з точністю до ізоморфізму існує 4 простих графа з 3 вершинами, 11 – з 4 вершинами і 34 з 5 вершинами.

Приклад 21. Описати матриці суміжності, Кіркгофа та інцидентності повних графів і дводольних графів. Що можна сказати про ці матриці простого графа та його доповнення?

Приклад 22. Довести, що реберний граф повного графа K_n з n вершинами має n(n – 1)/2 вершин і є регулярним степеня 2n – 4. Одержати аналогічні результати для графів K_{m, n}.

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

Приклад 24. Реберним графом простого графа G називають граф L(G), вершини якого однозначно зіставлені ребрам графа G, а дві вершини в L(G) суміжні тоді й лише тоді, коли відповідні ребра мають спільну вершину в G. Показати, що реберні графи графів на рисунку ізоморфні. Знайдіть вираз для числа ребер графа L(G) через степені вершин графа G.

Приклад 25. Зобразити всі кубічні (регулярні степеня 3) графи з не більше ніж 8 вершинами.

Приклад 26. Наведіть приклади (якщо це можливо):

а) дводольного графа, що є регулярним;

б) кубічного графа з 9 вершинами;

в) простого графа з n вершинами і (n – 1)(n – 2)/2 ребрами;

г) простого графа, ізоморфного своєму реберному графу;

д) простого графа, доповнення якого ізоморфне реберному графу;

е) чотиризв’язних графів, які є регулярними степеня 4.

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

Приклад 28. Простий граф, ізоморфний своєму доповненню (доповнення графа G має ті самі вершини, і вершини в суміжні тоді і тільки тоді, коли вони не суміжні в G) називаються самодоповнювальними. Довести, що кількість вершин самодоповнювального графа дорівнює 4k або 4k + 1. Знайти самодоповнювальні графи з 4 і 5 вершинами.

Приклад 29. Довести, що серед 6 осіб завжди знайдуться троє таких, які знають один одного або жоден з них не знає двох інших.

Приклад 30. Довести, що реберний граф простого ойлерового графа є ойлеровим. Якщо відомо, що реберний граф простого графа G є ойлеровим, то чи можна звідси вивести, що сам граф G є ойлеровим?

Приклад 31. Довести таке: коли граф G зв’язний і має k > 0 вершин непарного степеня, то мінімальна кількість ланцюгів, які не мають спільних ребер і об’єднання яких містить кожне ребро графа G, дорівнює k/2; як частковий випадок вивести, що граф є напівойлеровим (не обов’язково замкненим ланцюгом) тоді і тільки тоді, коли в ньому не більше двох вершин мають непарний степінь.

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

Приклад 33. Розглянемо скінченний зв’язний граф G = (V, E) на площині (V – множина вершин графа, G, E – множина його ребер, |V| = n, |E| = m). Припустимо, що ребра цього графа не перетинаються поза вершинами. Довести, що обмежена графом G область складається з m – n + 1 многокутників.

Приклад 34. Узагальнення теореми Ойлера. Нехай G – плоский граф з n вершинами, m ребрами, f гранями і k компонентами зв’язності. Довести, що n + f = m + k + 1.

Приклад 35. Нехай G зв’язний плоский граф з n  3 вершинами і m ребрами. Довести, що m  3n – 6.

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

Приклад 37. Довести, що графи K₅ і K_{3, 3} не плоскі.

Приклад 38. Довести, що не існує графа, степені всіх вершин якого різні.

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

Приклад 40. Лісом називають граф, який не містить циклів. Зв’язний ліс називають деревом. Довести, що дерево з n – 1 ребром має n вершин.

Приклад 41. Довести, що зв’язний граф з n вершинами і n – 1 ребром є деревом.

Приклад 42. Нехай G ліс з n вершинами і k деревами. Довести, що G має n – k ребер.

Приклад 43. Довести, що існує 512 орієнтованих графів з трьома вершинами. Скільки існує орієнтованих графів з n вершинами?

Приклад 44. Алгоритм Флері. Нехай G ойлеровий граф. Тоді наступна процедура завжди можлива і призводить до ойлерового ланцюга графа G. Виходимо з довільної вершини і рухаємося по ребрах графа згідно з такими правилами: а) стираємо ребра по мірі їх проходження, а також стираємо ізольовані вершини, які при цьому утворюються; б) на кожному кроці йдемо мостом лише тоді, коли немає інших можливостей. (Ребро зв’язного графа є мостом, якщо після його вилучення граф стає незв’язним). За допомогою алгоритму Флері знайти ойлеровий ланцюг у графі на рисунку.

Приклад 45. Для яких чисел m і n графи K_n та K_{m, n} є ойлеровими? Чи серед платонових графів (графів, відповідних правильним многогранникам: тетраедр, куб, октаедр, додекаедр, ікосаедр) є ойлерові? Якщо так, то знайдіть у них ойлерові ланцюги.

Приклад 46. Довести, що кожне дерево є дводольним графом. Які дерева є повними дводольними графами?

Приклад 47. Алгоритм Краскала для знаходження в зв’язному зваженому графі (G, w) каркаса мінімальної ваги. 1. Будуємо граф T₁, який складається з ребра найменшої ваги графа (G, w) та відповідних цьому ребру вершин. 2. Якщо граф T_i вже побудований і i  n + 1, то будуємо граф T_{i + 1}, долучаючи до графа T_i ребро графа G, яке має найменшу вагу серед ребер, що не входять в T_i, яке не утворює циклів з ребрами з T_i. Довести, що ця побудова завжди можлива і дає каркас найменшої ваги.

Приклад 48. Знайдіть каркасні дерева у графах K₅, K_{3, 3}?

Приклад 49. Застосовуючи алгоритм Краскала, знайти каркасне дерево найменшої ваги для графа.

4

1

5

3

6

7

6

2