Графи-2 плоскі графи, формула Ейлера, 9-11 класи, Гуртки, Малий мехмат МДУ
Гурток 9-11 класів
Тема 7.2. Графи-2. Плоскі графи, формула Ейлера
Визначення.Граф називається зв'язковим, якщо для будь-яких двох вершин існує шлях, що їх з'єднує.
Визначення.Зв'язковий граф без циклів (замкнутих шляхів) називається деревом.
1. Доведіть, що в будь-якому дереві число вершин на одиницю більше від числа ребер. 2. Доведіть, що з будь-якого зв'язкового графа можна видалити частину ребер так, що залишиться дерево.
Визначення.Повним графом називається граф, в якому будь-які дві вершини з'єднані руба. Повний граф із n вершинами позначається K n .
3. Скільки ребер у графі K n ?Визначення.Граф називається плоским (планарним), якщо його можна зобразити на площині так, щоб ребра не перетиналися. 4. Чи запланований граф K 4?Позначення.Нехай дано граф на площині. Тоді У — число вершин, Р — число ребер, а Р — число граней, тобто. частин, куди ребра графа розбивають площину. 5. Доведіть формулу Ейлера для зв'язкового графа на площині: В − Р + Г = 2. 6. У квадраті відзначили 20 точок і з'єднали їх відрізками, що не перетинаються, один з одним і з вершинами квадрата так, що квадрат розбився на трикутники. Скільки вийшло трикутників? 7. Доведіть, що а) для зв'язкового графа на площині 2Р ≥ 3Г; б) для зв'язкового графа на площині Р ≤ 3В − 6; в) остання нерівність правильна для довільного графа на площині. [У всіх пунктах передбачається, що граф має хоча б три вершини (В ≥ 3). У вироджених випадках K 1 і K 2 ці нерівності є неправильними.] 8. Доведіть, що граф K 5 не є планарним. 9. Є три будиночки та три колодязі. Чи можна з'єднати кожен будиночок з кожною криницею стежкою так, щоб стежки не перетиналися?
Граф, що виникає у задачі 9, називається K 3,3. Графи K 5 і K 3,3певному сенсі вичерпують усі можливі непланарні графи. А саме, вірна теорема Понтрягіна - Куратовського: граф не є планарним тоді і тільки тоді, коли він містить як підграф або K 5, або K 3,3, можливо, з додатковими вершинами на ребрах. 10. Кожне ребро повного графа з 11 вершинами пофарбоване в один із двох кольорів: червоний або синій. Доведіть, що або червоний, або синій граф не є плоским.Визначення.Ступенем вершини графа називається кількість ребер, що входять до неї. 11. Доведіть, що в плоскому графі є вершина, ступінь якої не перевищує 5. 12. Доведіть теорему про п'ять фарб: вершини будь-якого плоского графа можна розфарбувати не більше, ніж 5 кольорів так, що будь-які дві з'єднані ребром вершини будуть різного кольору. Вірна сильніша теорема про чотири фарби. Її довели К. Аппель та В. Хакен за допомогою ЕОМ у 1976 році.