Задачі для самостійного розв'язування

ГРАФИ

1. В якійсь країні є 9 міст з назвами 1, 2, 3, 4, 5, 6, 7, 8, 9. Мандрівник
виявив, що два міста з'єднані авіалінією в тому й тільки тому випадку,
коли двозначне число, складене із цифр — назв цих міст, ділиться на 3. Чи можна з міста 1 дістатися в місто 9?

Розв'язання

Накреслимо на­ступну схему: кожне місто позначимо точ­кою, а авіалінії — лініями, що з'єднують відповідні точки. Те­пер стає очевидним, що з міста 1 до міста 9 дістатися не можна.

 

Означення. Скінченна сукупність точок, деякі з яких з'єднані одна з одною лініями, називається графом. Ці точки називаються вершинами графа, а вказані лінії — ребрами графа.

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

Властивості графів не залежать від того, з'єднані вершини відрізками чи кривими лініями. Важливо лише, які вершини з'єднані, а які — ні.

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

Кількість ребер, що виходять з даної вершини графа, називаються степе­нем вершини.

Число непарних вершин довільного графа — парне. Справді, склавши сте­пені всіх вершин, отримаємо число, вдвічі більше від числа ребер графа, тобто парне число. Але сума декількох цілих чисел парна тоді й тільки тоді, коли кількість непарних доданків парна.

 

2. В якійсь країні 15 міст. Чи можна їх з'єднати авіалініями так, щоб було 4 міста, кожне з яких з'єднане з трьома іншими, 8 міст, кожне з яких з'єднане з шістьма іншими, і 3 міста, кожне з яких з'єднане з п'ятьма іншими?

Розв'язання

Якби це було можливим, то можна було б накреслити граф з 15 верши­нами, чотири з яких мали б степінь 3, вісім — степінь 6, три — степінь 5. Тоді загальна кількість непарних вершин була б непарною, що неможливо.

 

3. Певний архіпелаг складається з 2003 островів. З кожного острова виходить 1, 3 або 5 пароплавних ліній. Чи правда, що є пароплавна лінія, що з'єднує якийсь острів із зовнішнім світом?

Розв'язання

Якби це було не так, то можна було б накреслити граф з 2003 вершина­ми, кожна з яких мала б непарний степінь, що неможливо.

 

4. Чи може в державі, в якій з кожного міста виходить 3 дороги, бути рівно 100 доріг?

Розв'язання

Розглянемо граф із k вершинами, в якому з кожної вершини виходить 3 ребра. Тоді загальна кількість ребер дорівнює . Але для кожного k N . Отже, відповідь на питання за­дачі негативна.

 

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

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

 

5. На одній ділянці землі побудували три будинки А, В i С і вирили три криниці X, Y, Z. Господарі будинків пере­сварилися між собою і вирішили прокласти три стежки до криниць так, щоб на шляху до криниць і назад їм не доводилося зустрічатися один з од­ним. Чи можливо це?

Розв'язання

Відповідь на питання задачі залежить від того, чи буде відповідний граф плоским, тобто чи можна провести ребра графа так, щоб вони не пе­ретинались ніде, крім вершини графа А, В, С, X, Y, Z. Розв'я­зання спирається на наступну теорему Жордана.

 

Теорема. Нехай К — неперер­вна замкнута лінія на площині. Лінія К ділить площину на внутрішню і зовнішню області так, що довільна неперервна крива l, що з'єднує довільну точку Р внутрішньої області з деякою точкою Q зовнішньої області, перетинає К.

Доведення теореми досить складне, тому не будемо його тут наводити. З теореми Жордана випливає, що якщо довільні дві точки замкнутої лінії К, наприклад А і Y, з'єднати кривою AY, що не має з К спільних точок, відмінних від А і Y, то вся ця крива, за винятком її кінців, лежить або всере­дині К, або зовні.

Нехай тепер на замкнутій лінії К маємо чотири точки, розташовані в порядку А, В, Y, Z і проведені лінії A Y і BZ, що не перетинаються між со­бою. Тоді, за теоремою Жор­дана, обов'язково одна з них (нехай AY) лежить усередині К, а друга (BZ) зовні К. Не­хай тепер на лінії К маємо шість точок, розташованих у порядку А, X, В, Y, С, Z. Тоді три криві AY, BZ, CX не мо­жуть перетинатися. Справді, ці три криві повинні бути роз­ташованими удвох областях — внутрішній і зовнішній, по відношенню до К;принаймні дві з них попадуть в одну об­ласть, а тому обов'язково бу­дуть перетинатися.

Припустимо тепер, що граф, про який говорилося на початку, пло­ский. Накреслимо ребра АХ, ХВ, BY, YC, CZ, ZA так, щоб вони не перети­налися, і дістанемо на площині замкнуту криву. Але тоді ребра A Y, BZ, CX уже не можна буде провести так, щоб вони не перетинались. Отже, наш граф не є плоским, а тому відповідь на питання задачі є негативною.

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

 

6. Із столиці деякої країни виходить 21 дорога, із міста Далекого - одна, а із усіх інших міст — по 20. Доведіть, що зі столиці можна доїхати в Далеке (можливо, з пересадками).

Розв'язання

Розглянемо граф доріг цієї країни. Доведемо, що компонента зв'язності, що містить столицю, містить також і Далеке. Припустимо про­тилежне. Тоді в цій компоненті зв'язності степінь однієї вершини 21, а всіх інших — по 20. Це неможливо, оскільки кількість непарних вершин повинна бути парною. Суперечність доводить твердження задачі.

 

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

Розв'язання

Якщо накреслити граф так, як визначається в умові, то в кожну вер­шину, можливо за винятком першої і останньої, ми ввійдемо стільки ж разів, скільки і вийдемо з неї. Тому степені всіх вершин графа, крім двох, повинні бути парними.

Графи, розглянуті в попередній задачі, називаються ейлеровими у зв'язку із знаменитою задачею про кенігсберзькі мости, досліджену Леонардом Ейлером.

 

8. Схема мостів Кенігсберга зображена на рисунку. Чи можна здійснити прогулянку, про­ ходячи кожним мостом рівно один раз?

Розв'язання

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

Як бачимо, в цьому графі кількість не­парних вершин більша ніж 2. Тому цей граф не є ейлеровим. Отже, відповідь на питання задачі є негативною.

Зв'язний граф, що не має циклів, назива­ється деревом.

 

9. Доведіть, що в дереві є вершина, з якої виходить рівно одне ребро (така вер­шина називається висячою).

Розв'язання

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

 

10. Доведіть, що граф, в якому довільні дві вершини з'єднані рівно од­ним простим шляхом, є деревом. (Простим шляхом називається шлях, в якому жодне ребро не зустрічається двічі).

Розв'язання

Очевидно, що даний граф зв'язний. Якщо припустити, що в ньому є цикл, то тоді дві вершини цього циклу з'єднані принаймні двома про­стими шляхами. Протиріччя доводить твердження задачі.

 

11. В якійсь країні 101 місто і деякі з них зв'язані дорогами. При цьому кожні два міста з'єднує рівно один шлях. Скільки в цій країні доріг?

Розв'язання

З умови випливає, що граф доріг цієї країни є деревом. У цього дерева є висяча вершина. Видалимо її разом з ребром, яке з неї виходить. Граф, що залишається, теж є деревом. Тому в нього теж є висяча вершина, яку ми видалимо разом з ребром, що з неї виходить. Цю операцію виконаємо 100 разів, поки не дістанемо граф, що складається з однієї вершини. Оскільки щоразу видалялося одне ребро, то спочатку їх було 100.

 

12. Сітка має вигляд прямокутника розміром 50x600 клітинок. Яку найбільшу кількість ниток можна перерізати так, щоб сітка не розпалася на шматки?

Розв'язання

Будемо розглядати сітку як граф, вершинами якого є вузли сітки, а ребра — нитками. Будемо видаляти ребра цього графа так, щоб він залишався зв'язним, до того часу, поки це можливо. Зауважимо, що якщо в графі є цикл, то можна видалити довільне ребро цього циклу. Отже, ми не зможемо видалити жодного ребра тільки тоді, коли граф стане деревом. Підрахуємо тепер кількість ребер у цьому дереві. Кількість вершин зали­шається такою ж, як і на початку – 51 ∙ 601 = 30 651. Легко довести, що кількість ребер у дереві на 1 менше від кількості вершин. А спочатку їх було 601 ∙ 50 + 600 ∙ 51 = 60 650. Отже, можна видалити 30 000 ребер, тоб­то в сітці можна перерізати 30 000 ниток.

Правильно накреслений плоский граф розбиває площину на частини. По­значимо число цих частин через F, число вершин графа — через V і число ре­бер — через Е.

Теорема (Ейлера). Для правильно накресленого зв'язного плоского графа має місце рівність V – E + F = 2.

Доведення

Повторимо міркування, використане під час розв'язування задачі про розрізання ниток сітки. Будемо видаляти ребра доти, поки не дістанемо дерево. Зрозуміло, що при цьому кількість вершин не зменшується на 1. Число частин площини також зменшується на 1. Тому величина V – E + F є інваріантом. Оскільки, щоб отримати дерево, V – E = 1 і F = 1, то V–E+F= 2, а тому і для початкового графа також виконується ця рівність.

 

13. У квадраті позначили 20 точок і з'єднали їх відрізками, що не перетинаються, одна з одною і з вершинами квадрата так, щоб квадрат розбив­ся на трикутники. Скільки дістали трикутників?

Розв'язання

Позначені точки і вершини квадрата будемо вважати вершинами гра­фа, а відрізки і сторони квадрата — ребрами плоского графа. Для кожної частини, на які граф розбиває площину, підрахуємо число ребер, що її об­межує, і всі здобуті числа додамо. Оскільки кожне ребро розділяє дві час­тини, то в результаті дістаємо подвоєне число ребер. Оскільки всі частини площини, крім звільненої, — трикутники, а зовнішня частина обмежена чотирма ребрами, то маємо 3(F – 1) + 4 = 2 E, тобто . Зауважимо, що число вершин нашого графа дорівнює 24. Тоді, за формулою Ейлера, маємо: , звідки F = 43. Отже, число трикутників, на які розбивається квадрат, дорівнює 42.

Орієнтованим називається граф, на ребрах якого розставлені стрілки.

 

14. В якійсь країні є столиця і ще 100 міст. Деякі міста (у тому числі й столиця) з'єднані дорогами з одностороннім шляхом. Із кожного нестоличного міста виходить 20 доріг і в кожне таке місто входить 21 дорога. Доведіть, що в столицю не можна приїхати з жодного міста.

Розв'язання

Нехай у столицю входить п доріг. Тоді загальна кількість вхідних доріг дорівнює 21 ∙ 100 + п, а загальна кількість вихідних доріг не більша від 200 ∙ 100 + (100 – n). Тому 21 ∙ 100 + n ≤ 20 ∙ 100 + (100 – n), тобто 2 n ≤ 0 і n = 0.

 

15. В якійсь країні всі міста з'єднані між собою дорогами з одностороннім рухом. Доведіть, що знайдеться місто, з якого можна доїхати в будь-яке інше.

Розв'язання

Застосуємо індукцію за кількістю міст. Для n = 2 твердження задачі очевидне. Для доведення індуктивного переходу видалимо спочатку одне із міст. У силу індуктивного припущення існує місто А з потрібною вла­стивістю. Тепер, якщо у видалене місто веде хоча б одна дорога, то місто А — шукане, а якщо ні — то саме видалене місто має потрібну властивість.

 

Задачі для самостійного розв'язування

16. а) Дано шматок дроту довжиною 120 см. Чи можна, не ламаючи дроту, виготовити каркас куба з ребром 10 см?

б) Яку найменшу кількість разів все ж доведеться ламати дріт, щоб виготовити цей каркас?

 

17. Чи справді два графи ізоморфні, якщо:

а) у них 10 вершин, степінь кожної з яких дорівнює 9;

б) у них по 8 вершин, степінь кожної з яких дорівнює 3;

в) вони зв'язні, без циклів і мають по 6 ребер?

 

18. Доведіть, що в дереві довільні дві вершини з'єднані рівно одним простим шляхом.

 

19. В якійсь країні 30 міст, причому кожне з'єднане з кожним іншим дорогою. Яку найбільшу кількість доріг можна закрити на ремонт так, щоб з кожного міста можна було проїхати в кожне інше?

 

20. Доведіть, що для плоского зв'язного графа справедлива нерівність

E ≤ 3 V – 6.

 

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

 

22. Доведіть, що граф, у якому 10 вершин, степінь кожної з яких дорівнює 5, не плоский.

 

23. На площині дано 100 кіл, що складають зв'язну фігуру. Доведіть, що фігуру можна накреслити, не відриваючи олівця від паперу і не прово­дячи двічі одну й ту ж лінію.

 

24. Кожен із 102 учнів однієї школи знайомий не менше ніж із 68 іншими. Доведіть, що серед них знайдуться четверо, які мають однакову кількість знайомих.

 

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

 

26. Кожне з ребер повного графа із 17 вершинами пофарбоване в один
з трьох кольорів. Доведіть, що є три вершини, всі ребра між якими одного
кольору.

 

27. В одній державі 100 міст і кожне з'єднане з кожним містом з одно­
стороннім рухом. Доведіть, що можна змінити напрямок руху на одній дорозі так, щоб з кожного міста можна було доїхати до будь-якого іншого.

 

28. В одній країні 101 місто. Кожне місто з'єднане з кожним дорогою з одностороннім рухом, причому в кожне місто входить 50 доріг і з кожного міста виходить 500 доріг. Доведіть, що з кожного міста можна доїхати
в довільне інше місто, проїхавши не більше ніж двома дорогами.

 

29. Ребра графа пофарбовані в чотири кольори так, що в кожного шляху із трьох ребер перше і третє ребро пофарбовані в різні кольори (по­чаток і кінець шляху можуть співпадати). Доведіть, що вершини цього
графа можна пофарбувати в п'ять кольорів так, щоб кожні дві з'єднані
ребром вершини були пофарбовані в різні кольори.

 

30. а) Через декілька років після розпаду Зюйдвестівської імперії на
16 князівств з'ясувалося, що кожне князівство дружить з трьома князів­ствами і ворогує з усіма іншими. Чи можна розбити ці князівства на 8 пар
дружніх князівств?

б) Знайдіть найменшу кількість вершин графа, степені всіх вершин якого дорівнюють 3 і вершини якого не можна розбити на пари, з'єднані між собою.