Теорія графів

ВОЛОДИМИРСЬКИЙ ДЕРЖАВНИЙ ПЕДАГОГІЧНИЙ УНИВЕРСИТЕТ.

РЕФЕРАТ.

«ТЕОРІЯ ГРАФОВ».

Выполнила:

Зудина Т.В.

Володимир 2001.

1.

Введение

.

2. Історія виникнення теорії графов.

3. Основні визначення теорії графов.

4. Основні теореми теорії графов.

5. Завдання застосування теорії графов.

6. Застосування теорії графів в шкільному курсі математики.

7. Додаток теорії графів у різноманітних галузях науку й техники.

8. Останні досягнення теорії графов.

9. Вывод.

§ 1. ІСТОРІЯ ВИНИКНЕННЯ ТЕОРИИ ГРАФОВ.

Родоначальником теорії графів прийнято вважати математика Леонарда Эйлера (1707−1783). Історію виникнення цієї теорії можна простежити по листуванні великого вченого. Ось переклад латинського тексту, який узятий із листи Эйлера до італійському математику і інженеру Маринони, відправленого з Петербурга 13 березня 1736 року [див. [5]стр. 41−42]:

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

Питання це, хоч і банальний, видався мені, проте, гідним уваги тим, що його рішення недостатні ні геометрія, ні алгебра, ні комбинаторное мистецтво… Після тривалих роздумів я знайшов легке правило, заснований в цілком переконливому доказі, з допомогою якого переважають у всіх завданнях що така відразу ж визначити, може бути зроблений такий обхід через яке завгодно число як і завгодно розташованих мостів або може. Кенигсбергские ж мости розташовані тож їхній можна ось на чому малюнку [мал.1], у якому A позначає острів, а B, З і D — частини континенту, відмежовані одне від друга рукавами річки. Сім мостів є такі літерами a, b, з, d, e, f, g " .

(РИСУНОК 1.1).

Що стосується виявленого їм способу виконувати завдання такого роду Эйлер писав [див. [5]стр. 102−104]:

" Таке рішення за своїм характером, очевидно, маємо замало ставлення до математиці, і мені незрозуміло, чому слідує радше від математика очікувати цього заходу, ніж від будь-якої іншої людини, оскільки це рішення підкріплюється самим лише міркуванням, і немає необхідності залучати до перебування цього заходу будь-які закони, властиві математиці. Отже, я — не знаю, як виходить, питання, мають зовсім небагато ставлення до математиці, скоріш дозволяється математиками, ніж іншими " .

Тож чи можна обійти Кенигсбергские мости, проходячи лише одне раз через кожен із мостів? Щоб знайти відповіді, продовжимо лист Эйлера до Маринони:

" Питання у цьому, щоб визначити, чи можна обминути всі ці сім мостів, проходячи через кожен лише один раз, чи ні. Моє правило призводить до наступному вирішенню цього вопроса.

Насамперед, треба дивитися, скільки є ділянок, розділених водою, — таких, які мають іншого переходу з однієї в інший, інакше як міст. У цьому прикладі таких ділянок чотири — A, B, З, D. Далі потрібно розрізняти, чи є число мостів, які ведуть цим окремих ділянок, четным чи нечетным.

Так було в нашому випадку до дільниці A ведуть п’ять мостів, а до остальным.

— по три мосту, т. е. Кількість мостів, які ведуть окремих ділянок, нечетно, а цієї однієї вже на вирішення завдання. Коли визначено, застосовуємо таке правило: якби число мостів, які ведуть кожному окремому ділянці, було четным, тоді обхід, про який мова, було б може бути, й те водночас можна було б розпочати цей обхід з будь-якої світової участка.

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

Обгрунтування вищенаведеного правила можна знайти у листі Л. Эйлера до свого друга Элеру від 3 квітня цього року. Ми перескажем нижче уривок із листа цього письма.

Математик писав, що перехід може бути, якби ділянці розгалуження річки є трохи більше двох областей, у яких веде парне число мостів. А, щоб простіше уявити собі цю, будемо прати на малюнку вже пройдені мости. Легко перевірити, коли ми почнемо рухатися відповідно до правилами Эйлера, перетнемо один міст і зітремо його, то, на малюнку буде зображений ділянку, де знову є трохи більше двох областей, у яких веде парне число мостів, а за наявності областей з непарною числом мостів ми розташовуватися на одній із них. Продовжуючи рухатися таке інше, пройдемо крізь ці мости за одним разу.

В історії з мостами міста Кенігсберга має сучасне продовження. Відкриємо, наприклад, шкільний підручник з математики під редакцією Н. Я. Виленкина для класу. У ньому сторінка 98 подається рубрика розвитку пильності і кмітливості знайдемо завдання, має безпосередній стосунок до тієї, який колись вирішував Эйлер.

Завдання № 569. На озері перебуває сім островів, які з'єднані між собою оскільки показано малюнку 1.2. Та на якій острів повинен доставити мандрівників катер, що вони могли подолати на кожному мосту і лише одне раз? Чому не можна доставити мандрівників острова A?

(РИСУНОК 1.2).

Рішення. Оскільки це завдання подібна завданню про Кенигсбергских мости, то, при її рішенні ми також скористаємося правилом Эйлера. Через війну одержимо наступний відповідь: катер повинен доставити мандрівників острова E чи F, що вони змогли подолати на кожному мосту одного разу. З тієї самої правила Эйлера слід неможливість необхідного обходу, якщо він розпочнеться з острова A.

На закінчення відзначимо, що завдання про Кенигсбергских мости і такі їй завдання разом із сукупністю методів дослідження становлять дуже важливий у практичному відношенні розділ математики, званий теорією графів. Перша робота про графах належала Л. Эйлеру і з’явилася 1736 року. Надалі над графами працювали Кеніг (1774−1833), Гамільтон (1805- 1865), із сучасних математиків — До. Берж, Про. Оре, А. Зыков.

§ 2. ОСНОВНІ ТЕОРЕМИ ТЕОРИИ ГРАФОВ.

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

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

Цю ухвалу можна сформулювати інакше: графом називається непорожнє безліч точок (вершин) і відрізків (ребер), обидва кінці яких належать заданому безлічі точок (див. рис. 2.1).

(РИСУНОК 2.1).

Надалі вершини графа ми позначати написом A, B, З, D. Іноді граф загалом будемо позначати однієї головній буквой.

Визначення 2.02. Вершини графа, які належать жодному ребру, називаються изолированными.

Визначення 2.03. Граф, який складається тільки з ізольованих вершин, називається нуль-графом.

Позначення: O «- граф з вершинами, яка має ребер (рис. 2.2).

(МАЛЮНОК 2.2).

Визначення 2.04. Граф, у якому кожне подружжя вершин з'єднана руба, називається полным.

Позначення: U «- граф, що з n вершин і ребер, що з'єднують різноманітні пари цих вершин. Такий граф можна подати як n-угольник, у якому проведені всі діагоналі (рис. 2.3).

(МАЛЮНОК 2.3).

Визначення 2.05. Ступенем вершини називається число ребер, яким належить вершина.

Позначення: p (A) — ступінь вершини A. Наприклад, малюнку 2.1: p (A)=2, p (B)=2, p (C)=2, p (D)=1, p (E)=1.

Визначення 2.06. Граф, ступеня всіх k вершин якого однакові, називається однорідним графом ступеня k.

На малюнку 2.4 і 2.5 зображені однорідні графи другої і третьої степени.

(МАЛЮНОК 2.4 і 2.5).

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

На малюнку 2.6 зображений вихідний граф G, що з чотирьох вершин й трьох відрізків, але в малюнку 2.7 — доповнення даного графа — граф G " .

(МАЛЮНОК 2.6 і 2.7).

Ми, що у малюнку 2.5 ребра AC і BD перетинаються у точці, не що є вершиною графа. Але трапляються випадки, коли цей граф необхідно уявити на площини у такому вигляді, що його ребра перетиналися лише в вершинах (це буде розглянутий докладно далі, в параграфі 5).

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

Наприклад, малюнку 2.8 показаний плаский граф, изоморфный (рівний) графу малюнку 2.5. Проте, зауважимо, що ні кожен граф є пласким, хоча зворотне твердження вірно, т. е. будь-який плаский граф можна у звичайному виде.

(МАЛЮНОК 2.8).

Визначення 2.09. Багатокутник плоского графа, він всередині себе жодних вершин чи ребер графа, називають його гранью.

Поняття плоского графа і межі графа застосовується під час вирішення завдань на «правильне «розфарбовування різних карт (докладніше звідси — в § 4).

Визначення 2.10. Шляхом від A до X називається послідовність ребер, провідна від A до X, така, що щодва сусідніх ребра мають загальну вершину, й ніяка ребро не зустрічається більше раза.

Наприклад, малюнку 2.9 дано граф G ", у якому прокладено шлях від З до H: (З, F); (F, B); (B, A); (A, H) чи (З, D); (D, E); (E, A); (A, H).

(МАЛЮНОК 2.9).

Визначення 2.11. Циклом називається шлях, у якому збігаються початкова й кінцева точка.

Ось приклад циклу, прокладеного на графі G (рис. 2.9): (A, B); (B, F); (F, З); (З, D); (D, E); (E, A).

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

Визначення 2.13. Довжиною шляху, прокладеного на циклі, називається число ребер цього пути.

Приклад: на графі G (рис. 2.9) прокладено простий цикл (A, B); (B, F); (F, З); (З, D); (D, E); (E, A) довжина шляху цього циклу дорівнює 6.

Визначення 2.14. Дві вершини A і B в графі називаються зв’язковими (незв'язними), якщо у неї існує (немає) шлях, провідний з A в B.

Визначення 2.15. Граф називається зв’язковим, якщо кожні дві його вершини связны; Якщо ж в графі знайдеться хоча тільки пара незв’язних вершин, то граф називається несвязным.

(МАЛЮНОК 2.10 і 2.11).

На малюнку 2.10 зображений зв’язний граф; малюнку 2.11 — незв’язний (т. до. існує мінімум одна пара незв’язних вершин — A і D).

Визначення 2.16. Деревом називається зв’язний граф, він циклов.

Тривимірної моделлю графа-дерева служить, наприклад, справжнє дерево з його вигадливо розгалуженої кроною; ріка і його притоки також утворюють дерево, але вже настав пласке — лежить на поверхні землі (рис. 2.12).

(МАЛЮНОК 2.12).

Визначення 2.17. Незв’язний граф, який складається лише з дерев, називається лесом.

Приклад: малюнку 2.13 зображений ліс, трійка деревьев.

(МАЛЮНОК 2.13).

Визначення 2.13. Дерево, все n вершин якої мають номери від 1 до n, називають деревом з перенумерованными вершинами.

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

§ 3. ОСНОВНІ ТЕОРЕМИ ТЕОРИИ ГРАФОВ.

Маючи наведені вище визначення теорії графів, наведемо формулювання і речові докази теорем, які потім знайдуть свої докладання під час вирішення задач.

Теорему 3.1. Подвоєна сума ступенів вершин будь-якого графа дорівнює числу його ребер.

Доказ. Нехай А1, А2, А3, …, An — вершини даного графа, a p (A1), р (А2), …, p (An) — ступеня цих вершин. Підрахуємо число ребер, збіжних у кожному вершині, і просуммируем ці числа. Це віднайденню суми ступенів всіх вершин. За такої підрахунку кожне ребро буде враховано двічі (воно завжди з'єднує дві вершины).

Звідси випливає: p (A1)+р (А2)+ … +p (An)=0,5N, чи 2(p (A1)+р (А2)+ … +p (An))=N, де N — число ребер. (.

Теорему 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.1 пояснює умова теореми. На зображеному графі все 5 простих циклів четные.

(РИСУНОК 3.1).

Суть теореми у цьому, що у цьому графі неможливо було знайти цикл (як простий, і непростий) нечетной довжини, тобто у якому парне число ребер.

Теорему 3.6. А, щоб граф був эйлеровым, необхідне й досить, щоб було зв’язковим і всі його вершини мали четную степень.

Теорему 3.7. Щоб на зв’язковому графі можна було б прокласти ланцюг АВ, що містить усі його ребра з точністю за одним разу, необхідне й досить, щоб Проте й У були єдиними непарними вершинами цього графа.

Доказ цієї теореми дуже цікаво й притаманно теорії графів. Його слід вважати конструктивним (зверніть увагу, як •використана у своїй теорема 3.6). Аби довести до вихідному графу присоединяем ребро (А, У); після цього є всі вершини графа стануть парними. Цей новий граф задовольняє всім умовам теореми 3.6, і тому у ньому можна прокласти эйлеров цикл ?. Навіть якщо нині у цьому циклі видалити ребро (А, У), то залишиться бажана ланцюг АВ. (.

У цьому вельми цікавому прийомі грунтується доказ наступній теореми, яку вважати узагальненням теореми 3.7.

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

Теорему 3.9. Різноманітних дерев з n перенумерованными вершинами можна побудувати nn-2.

Що стосується докази цієї теореми зробимо одне зауваження. Ця теорема відома, переважно, і висновок англійського математика А. Кэли (1821—1895). Графы-деревья здавна привертали увагу учених. Сьогодні двоичные дерева використовуються як математиками, чи біологами, хіміками, фізиками і інженерами (докладніше звідси — в параграфі 6).

Теорему 3.10. Повний граф з п’ятьма вершинами перестав бути плоским.

Доказ. Скористаємося формулою Эйлера: В-Р+Г=2, де У — число вершин плоского графа, Р — число його ребер, Р — число граней. Формула Эйлера справедлива для пласких зв’язкових графів, у яких жодного з многоугольников не лежить всередині іншого. На малюнку 3.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 + …).

Зрозуміло, що (3?3+3?4+3?5+…) < (3?3+4?4+ 5?5+…) чи 3 Г.