З ім'ям Ейлі-ра, є завдання про трьох будиночках і трьох колодязях.
Завдання. Три сусіда мають три загальних колодязя. Чи можна провести непересека-ються доріжки від кожного будинку до кожного колодязя (рис. 1)?
Для вирішення цього завдання скористаємося теоремою, доведеною Ейлером в 1752 році.
Теорема. Якщо багатокутник розбитий на кінцеве число багатокутників так, що будь-які два багатокутника розбиття або не мають спільних точок, або мають загальні вершини, або мають спільні ребра, то має місце рівність
де В - загальне число вершин, Р - загальне число ребер, Г - число багатокутників (граней).
Доведення. Доведемо, що рівність (*) не зміниться, якщо в якомусь многоугольнике даного розбиття провести діагональ (рис. 2, а).
Дійсно відс-но, після проведення такої діагоналі в новому розбитті буде У вершин, Р + 1 ребер і кількість багатокутників збільшиться на одиницю. Отже, маємо
В - (Р + 1) + (Г + 1) = В - Р + Г.
Користуючись цією властивістю, проведемо діагоналі, що розбивають входячи щие багатокутники на трикутники, і для отриманого розбиття поки-жем здійсненність співвідношення (*) (рис. 2, б). Для цього будемо послідовно-вательно прибирати зовнішні ребра, зменшуючи кількість трикутників. При цьому можливі два випадки:
а) для видалення трикутника ABC потрібно зняти два ребра, в на-шем випадку AB і BC;
б) для видалення трикутника MKN потрібно зняти одне ребро, в нашому випадку MN.
В обох випадках рівність (*) не зміниться. Наприклад, в першому випадку після видалення трикутника граф буде складатися з В-1 вершин, Р-2 ребер і Г-1 багатокутника:
(В - 1) - (Р + 2) + (Г-1) = В - Р + Г.
Самостійно розгляньте другий випадок.
Таким чином, видалення одного трикутника не змінює рівності (*). Продовжуючи цей процес видалення трикутників, в кінці кінців ми прийдемо до розбиття, що складається з одного трикутника. Для такого розбиття В = 3, Р = 3, Г = 1 і, отже, B - Р + Г = 1. Значить, рівність (*) має місце і для вихідного розбиття, звідки я остаточно-кові отримуємо, що для даного розбиття багатокутника справедливо співвідношення (*).
Зауважимо, що співвідношення Ейлера не залежить від форми багатокутників. Багатокутники можна деформувати, збільшувати, зменшувати або навіть викривляти їх боку, аби при цьому не стати жертвою розривів сторін. Співвідношення Ейлера при цьому не зміниться.
Приступимо тепер до вирішення завдання про трьох будиночках і трьох колодязях.
Рішення. Припустимо, що це можна зробити. Відзначимо будиночки точками Д1. Д 2. Д3. а колодязі - точками К1. К2. К3 (рис. 1). Кожну точку-будиночок з'єднаємо з кожною точкою-колодязем. Отримаємо дев'ять ребер, які попарно не перетинаються.
Ці ребра утворюють на площині багатокутник, розділений на бо-леї дрібні багатокутники. Тому для цього розбиття має виконан-тися співвідношення Ейлера В - Р + Г = 1. Додамо до досліджуваних гра-ням ще одну - зовнішню частину площині по відношенню до багатокутника. Тоді співвідношення Ейлера набуде вигляду В - Р + Г = 2, причому В = 6 і Р = 9. Отже, Г = 5. Кожна з п'яти граней має принаймні чотири ребра, оскільки, за умовою задачі, жодна з доріжок НЕ повинна безпосередньо з'єднувати два будинки або два колодязі. Так як кожне ребро лежить рівно в двох гранях, то кількість ре-бер повинно бути не менше (5 # 8729; 4) / 2 = 10, що суперечить умові, за яким їх число дорівнює 9. Отримане протиріччя показує, що від-вет в завданню негативний - не можна провести непересічні доріжки від кожного будиночка до кожного колодязя.
1. Граф називається зв'язковим. якщо будь-які дві його вершини можна сої-дініть ламаної, що складається з ребер графа. Намалюйте зв'язкові і незв'язний-ні графи.
2. Зв'язковий граф, який не містить жодної замкнутої ламаної, називається деревом. Намалюйте графи, які є деревами.
3. Доведіть, що в графі, що є деревом, будь-які дві вершини можна з'єднати тільки однієї ламаної.
4. Доведіть, що для будь-якого дерева, що має У вершин і Р ребер, справедливо співвідношення Ейлера: В - Р = 1.
5. Наведіть приклади графів, для яких В - Р ¹ 1.
6. Граф, який не містить жодної замкнутої ламаної, називаючи-ється лісом. Нехай ліс складається з n дерев і має В вершин і Р ре-бер. Чому дорівнює В - Р?
7. Намалюйте графи, для яких В - Р одно: а) 0; б) 1; в 2; г) -1; д 2.
8. Вкажіть яку-небудь розбиття опуклого чотирикутника на опуклі чотирикутники.
9. Доведіть, що для довільного розбиття чотирикутника на чотирикутники виконується рівність В - Г = 3.
10. Вкажіть яку-небудь розбиття опуклого п'ятикутника на опуклі п'ятикутники.
11. Вкажіть яку-небудь розбиття трикутника на семикутники.
12. Усередині n - кутника взяті m точок. Ці точки і вершини багато-кутника з'єднані відрізками так, що вихідний багатокутник розбиваючи-ється на трикутники. Доведіть, що при цьому число трикутників дорівнює n + 2 m- 2.
13. Багатокутник розбитий на кінцеве число багатокутників так, що в кожній вершині сходиться три ребра. Скільки при цьому є вер-шин і граней, якщо число ребер одно: а) 6; б) 12; в) 15? Намалюйте такі розбиття.
14. Доведіть, що для будь-якого розбиття n -угольніка на m -угольнікі виконується рівність 2В + (2 - m) Г = n + 2.
15. У багатокутнику вирізали дірку в формі багатокутника. Частину розбили на багатокутники. Чому дорівнює В - Р + Г для цього розбиття?
16. Два сусіда мають: а) три загальних колодязя; б) чотири загальних колодязя. Чи можна провести непересека-ються доріжки від кожного будинку до кожного колодязя?
17. Три сусіда мають: а) два загальних колодязя; б) чотири загальних колодязя. Чи можна провести непересека-ються доріжки від кожного будинку до кожного колодязя?
18. Чотири сусіда мають чотири загальних колодязя. Чи можна провести непересека-ються доріжки від будиночків до криниць так, щоб кожен будиночок був з'єднаний з трьома колодязями і кожен колодязь з трьома будиночками?