ОСНОВНІ ТЕОРЕМИ ТЕОРІЇ ГРАФІВ - Студопедія
Спираючись на наведені вище визначення теорії графів, наведемо формулювання та докази теорем, які потім знайдуть свої додатки під час вирішення завдань.
Теорема 3.1. Подвоєна сума ступенів вершин будь-якого графа дорівнює числу його ребер.
Доказ. НехайА1,А2,А3, .An -вершини даного графа, a p(A1), р(А2), . p(An) – ступеня цих вершин. Підрахуємо число ребер, що сходяться у кожній вершині, і підсумуємо ці числа. Це рівнозначно знаходженню суми ступенів усіх вершин. При такому підрахунку кожне ребро буде враховано двічі (адже воно завжди з'єднує дві вершини).
Теорема 3.2. Кількість непарних вершин будь-якого графа парне.
Доказ. Нехайa1, a2, a3, …, ak-це ступені парних вершин графа, аb1, b2, b3, …, bm -ступеня непарних вершин графа. Сумаa1+a2+a3+…+ak+b1+b2+b3+…+bmрівно вдвічі перевищує число ребер графа. Сумаa1+a2+a3+…+akпарна (як сума парних чисел), тоді сумаb1+b2+b3+…+bmмає бути парною. Це можливо лише в тому випадку, якщоm —парне, тобто парним є число непарних вершин графа. чтд.
Ця теорема має чимало цікавих наслідків.
Слідство 1. Непарне число знайомих у будь-якій компанії завжди парне.
Слідство 2. Кількість вершин багатогранника, в яких сходиться непарне число ребер, парне.
Наслідок 3. Число всіх людей, які будь-коли потиснули руку іншим людям, непарне число разів, є парним.
Теорема 3.3. У будь-якому графі зnвершинами, деnбільше або дорівнює 2, завжди знайдуться дві або більше вершини з однаковими ступенями.
Доказ. Якщо граф маєnвершин, токожна з них може мати ступінь 0, 1, 2, . (n- 1). Припустимо, що у деякому графі всі його вершини мають різну ступінь, тобто,і покажемо, що цього не може. Справді, якщо р(А)=0,то це означає, щоА -ізольована вершина, і тому в графі не знайдеться вершиниХзі ступенем р(Х)=n-1.Справді, ця вершина повинна бути з'єднана з (n-1) вершиною, в тому числі і зА, але жАвиявилася ізольованою. Отже, у графі, що маєn вершин, не можуть бути одночасно вершини ступеня 0 і (n-1). Це означає, що зn вершин знайдуться дві, що мають однакові ступені. чтд.
Теорема 3.4. Якщо у графі зnвершинами (nбільше або одно 2) тільки одна пара має однаковий ступінь, то в цьому графі завжди знайдеться або єдина ізольована вершина, чи єдина вершина, з'єднана з іншими.
Доказ цієї теореми ми опускаємо. Зупинимося лише на деякому її поясненні. Зміст цієї теореми добре пояснюється завданням: група, що складається зnшколярів, обмінюється фотографіями. У певний момент часу з'ясовується, що двоє здійснили однакову кількість обмінів. Довести, що серед школярів є або один ще не починав обміну, або один, що вже завершив його.
Теорема 3.5. Якщо у графа всі прості цикли парної довжини, він не містить жодного циклу парної довжини.
Теорема 3.6. Для того, щоб граф був ейлеровим, необхідно і достатньо, щоб він був зв'язковим і всі його вершини мали парний ступінь.
Теорема 3.7. Для того щоб на зв'язному графі можна було б прокласти ланцюгАВ,містить всі його ребра в точності по одному разу, необхідно ідостатньо, щобАіВбули єдиними непарними вершинами цього графа.
Доказ цієї теореми дуже цікавий і притаманний теорії графів. Його також слід вважати конструктивним (зверніть увагу на те, як • використовується теорема 3.6). Для доказу до вихідного графа приєднуємо ребро (А,В); після цього всі вершини графа стануть парними. Цей новий граф задовольняє всім умовам теореми 3.6, і тому в ньому можна прокласти ейлерів циклΨ.І якщо тепер у цьому циклі видалити ребро (А,В),то залишиться шуканий ланцюгАВ.чтд.
На цьому цікавому прийомі ґрунтується доказ наступної теореми, яку слід вважати узагальненням теореми 3.7.
Теорема 3.8. Якщо даний граф є зв'язковим і має 2kвершин непарного ступеня, то в ньому можна провестиkрізних ланцюгів, що містять усі його ребра в сукупності рівно по одному разу.
Теорема 3.9. Різних дерев зnперенумерованими вершинами можна побудуватиn n -2.
Щодо доказу цієї теореми зробимо одне зауваження. Ця теорема відома в основному як висновок англійського математика А. Келі (1821-1895). Графи-дерева здавна привертали увагу вчених. Сьогодні двійкові дерева використовуються не тільки математиками, а й біологами, хіміками, фізиками та інженерами (докладніше про це – параграф 6).
Теорема 3.10. Повний граф із п'ятьма вершинами не є плоским.
Доказ. Скористаємося формулою Ейлера:В-Р+Г=2,деВ- число вершин плоского графа,Р- число його ребер,Г- число граней. Формула Ейлера справедлива для плоских зв'язкових графів, у яких жоден із багатокутників нележить усередині іншого. На малюнку 3.2, а зображено граф, якого формула не застосовна — заштрихований багатокутник перебуває всередині іншого. Праворуч наведено зображення графа, якого формула застосовна.
Цю формулу можна довести методом математичної індукції. Цей доказ ми опускаємо. Зауважимо лише, що формула справедлива й для просторових багатогранників. Нехай усі п'ять вершин графа з'єднані одна з одною (рис. 3.2). Зауважуємо, що на графі немає жодної грані, обмеженої лише двома ребрами. Якщо черезφ1позначити кількість таких граней, тоφ2=0. Далі міркуємо від неприємного, зокрема: припустимо, що досліджуваний граф плоский. Це означає, що йому вірна формула Эйлера. Число вершин у даному графіВ=5,число реберР=10, тоді число гранейГ=2-В+Р=2-5+10=7.
Це число можна подати у вигляді суми:Г=φ1+φ2+φ3+…, деφ3– число граней, обмежених трьома ребрами,φ4- число граней, обмежених чотирма ребрами і т.д.
З іншого боку, кожне ребро є межею двох граней, тому число граней дорівнює 2Р,в той же час 2Р=20=3φ3+4φ4+.. Помноживши рівністьГ=7=φ3+ φ4 + φ5 +… на три, отримаємо ЗГ=21=3( φ3 + φ4 + φ5 + …).
Чи не знайшли те, що шукали? Скористайтеся пошуком: