Марчук Людмила Василівна, учитель інформатики Черкаська загальноосвітня школа І-ІІІ ступенів

Між дев'ятьма планетами Сонячної системи встановлено космічний звязок. Рейсові ракети літають за такими маршрутами: ЗемляМеркурій Плутон Венера Уран НептунЮпитер Марс Сатурн Земля Меркурій; Плутон – Венера; Земля - Плутон; Плутон – Меркурій; Меркурій – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпітер – Марс; Марс – Уран. Чи можна долетіти на рейсових ракетах від Землі до Марсу?

Графи – це геометричні фігури, що складаються лише з точок і відрізків прямої чи кривих ліній. Точки називаються вершинами або вузлами графа, а лінії – ребрами графа. Завдання Знайдіть кількість ребер і вершин графа Вершин 4 Ребер-3 Вершин 5 Ребер-5 Вершин 4 Ребер-6 Вершин 8 Ребер-9 Вершин 7 Ребер-10 Вершин 5 Ребер

Степені вершин Степенем вершини графа називається кількість ребер, що виходять з вершини. Парні вершини - вершини, степінь яких є парним числом. Непарні вершини – вершини, степінь яких є непарним числом. Ізольована вершина – вершина степеня «0» Кінцевою або висячою називається вершина, яка має степінь «1»

в F C E D A Вершина G є ізольована. Вершина E, D є висячі. Вершини A, B мають степінь 3. Вершина F має степінь 2. Вершина C має степінь

Завдання Обчисліть степінь вершин графа А Б В Г

Ви напевно, зустрічалися із задачами, в яких потрібно накреслити якусь фігуру «одним розчерком пера»? Виявляється, що така задача не завжди може бути розв'язана. Вперше це питання дослідив в 1736 році великий математик Леонард Ейлер, коли розв'язував задачу про Кенігсберзькі мости Тому графи, які можна зобразити указаним способом називають Ейлеровими графами

Задача про Кенігсбергскі мости Філософ Іммануїл Кант, гуляючи по місту Кенігсбергу (зараз це місто називається Калінінград), поставив завдання (1736), відому в математиці як задача про сім Кенігсбергских мости: чи можна пройти по всіх цих мостах і при цьому повернутися в початкову точку так, щоб по кожному мосту пройти лише один раз. Рис.1.1 Кенігсберзькому мости Багато кенігсбержців намагалися вирішити цю задачу як теоретично, так і практично, під час прогулянок. Але нікому це не вдавалося, проте не вдавалося і довести, що це навіть теоретично неможливо

У 1736 році завдання про сім мостах зацікавила видатного математика, члена Петербурзької академії наук Леонарда Ейлера, про що він написав у листі італійському математику і інженеру Маріон від 13 березня 1736 року. У цьому листі Ейлер пише про те, що він зміг знайти правило, користуючись яким легко визначити, чи можна пройти по всіх мостах, не проходячи двічі по жодному з них (у разі семи мостів Кенігсберга це неможливо). На рис.1.2 зображена схема семи мостів Кенігсберга (зауважимо, що зараз залишилося тільки два з них)

Коли в усіх вузлах графа сходиться парне число ребер, тоді, пішовши від будь-якого вузла, можна обійти, або накреслити фігуру «одним розчерком пера». Такі фігури називаються унікурсальними. Фігуру, що має два непарних вузли, так само можна накреслити. Початок і кінець обходу тепер обов'язково знаходитимуться в непарних вузлах. Якщо ж фігура має непарні вузли один або більше двох, то накреслити її «одним розчерком пера» не вдається. У графа кенігсберзьких мостів усі чотири вузли непарні, тому «одним розчерком пера» ніяк не накреслити. в а Граф Кенигсбергских мостів мав чотири непарні вершини (тобто всі), отже, неможливо пройти по всіх мостах, не проходячи по жодному з них двічі

В ході міркувань Ейлер прийшов до наступних висновків: Число непарних вершин (вершин, до яких веде непарне число ребер) графа повинно бути парне. Не може існувати граф, який мав би непарне число непарних вершин. Граф з більш ніж двома непарними вершинами неможливо накреслити одним розчерком На спрощеній схемі частині міста (графі) мостам відповідають лінії (дуги графа), а частинам міста - точки з'єднання ліній (вершини графа). Якщо всі вершини графа парні, то можна, не відриваючи олівця від паперу, накреслити граф, при цьому можна починати з будь- якої вершини графа і завершити його в тій же вершині

Завдання Накресліть «одним розчерком пера» А Б В ГД

Пошук найкоротших шляхів на графі є одною з найважливіших задач теорії графів. Для незважених графів найкоротшим буде шлях, що містить найменшу кількість ребер. А для зважених графів найкоротшим буде шлях, на який витрачається найменша тривалість шляху. Зважений граф – граф, кожному ребру якого поставлено у відповідність деяке значення (вага). Тривалість шляху (t)- час, необхідний для проходженя шляху на данному графі

а в На поданому малюнку від т.А до т.В є три шляхи. Позначимо ці шляхи І 1, І 2, І 3. Обчислимо їх тривалість: T(І 1 )=11+5=16 T(І 2 )=6+7=13 T(І 3 )=3+13=16 Порівнявши шляхи для можна зробити висновок: найкорошим є шлях І

Знайдіть найкоротший шлях

Завдання Доповни граф, щоб утворилася унікурсальна лінія

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

Для ізоморфізму орієнтованих графів потрібно також, щоб напрямок ребер між вершинами з однаковими номерами був однаковим. (!) Можливі графи з деякими крайніми випадками: існування в орієнтованому графі 2-х ребер, що з'єднують одну і ту ж пару вершин у різних напрямках (зустрічається найчастіше); наявність в неорієнтованому графі декількох ребер між одними і тими ж двома вершинами (але це можна легко побороти); наявність в графі "петель" - ребер, що з'єднують вершину з самою собою. Завжди слід з'ясовувати, які з цих ситуацій можуть бути присутніми в даній задачі, і які з них можете отримати ви самі, проводячи перетворення графа. У цій лекції ми будемо припускати відсутність таких особливостей

Граф Геометрично граф можна представити як набір вершин (точок), визначені пари яких з'єднані лініями. Наприклад, мережа доріг, що з'єднує міста Е1, Е2, Е3, Е4, Е5 можна представити у вигляді графа таким чином: міста позначимо точками (вершинами), а дороги неорієнтованих лініями (рис.2.1) Неорієнтовані лінії означають наявність двостороннього руху між відповідною парою міст. Перетину лінією не вважаються вершинами. Рис.2.1 Граф мережі доріг

Таким чином, математично граф можна розглядати як безліч кружків і безліч з'єднувальних їх ліній. Кружки називаються вершинами графа, лінії зі стрілками - дугами, без стрілок - ребрами. Граф G (V, E) - сукупність кінцевої непорожньої безлічі елементів V (вершин) і кінцевої (можливо, порожньої) безлічі неупорядкованих пар елементів Е (дуг або ребер) з безлічі V. Залежно від наявності або відсутності орієнтації у пар елементів з множини V розрізняють графи орієнтовані, неорієнтовані (реберні), змішані. Граф є графом порядку n, якщо у нього - n вершин

Суміжність Нехай V1, V2 - вершини, е = (V1, V2) - з'єднує їх ребро (рис.2.3). Тоді вершина V1 і ребро е інцідентни, вершина V2 і ребро е також інцидентні. Рис.2.3 Суміжні вершини Дві вершини називаються суміжними, якщо вони з'єднані ребром / дугою (рис.2.3) Два ребра називаються суміжними, якщо вони з'єднані вершиною / вузлом (рис.2.4). Суміжні вершини - дві вершини, інцидентні одному ребру. Суміжні ребра - два ребра, інцидентні одній вершині

Безліч вершин, суміжних з вершиною V, називається безліччю суміжності вершини V і позначається Г + (V) (рис. 2.5). Число інцидентних вершині ребер називається степенем вершини і позначається P (X i). Вершина, ступінь якої дорівнює 0, називається ізольованою. Порожній граф - граф, що складається з декількох ізольованих вершин. Рис.2.5 Безліч суміжності

Орієнтований граф Граф називається орієнтованим (або орграфом), якщо деякі ребра мають напрямок (рис.2.6). Це означає, що в Орграф деяка вершина може бути з'єднана з іншою вершиною, а зворотного з'єднання немає. У разі орієнтованого графа елементи множини V називаються вузлами, а елементи множини Е - дугами. Орграф будемо позначати G = (V, e), де e - множина дуг. Кратні ребра - ребра, що зв'язують одну і ту ж пару вершин. Рис.2.6 Орієнтований граф За визначенням в Орграф немає петель і кратних дуг

Спрямований граф - орграф, що не має симетричних пар орієнтованих ребер. Рис.2.7 орграфа з трьома вершинами і трьома дугами На малюнку 2.7 наведені всі орграфи з трьома вершинами і трьома дугами, два останніх з них - спрямовані графи

Маршрути і шляхи графа Одне з найбільш простих властивостей, яким може володіти граф це властивість бути зв'язаним. У даному розділі розглядаються основні структурні властивості зв'язаних і незв'язаних графів. Маршрут в графі - послідовність вершин і ребер, що чередуються. Ця послідовність починається і закінчується вершиною, і кожне ребро послідовності інцидентне двом вершинам, одна з яких безпосередньо передує йому, а інша безпосередньо слідує за ним (рис.2.8) Рис.2.8 Граф для ілюстрації маршрутів

Зазначений маршрут з'єднує вершини Vo і Vn, і його можна позначити Vo, V1, V2,.., Vn (наявність ребер мається на увазі). Ця послідовність іноді називається (Vo-Vn) - маршрутом. Маршрут замкнутий, якщо Vo = Vn, і відкритий в іншому випадку. Ланцюг - маршрут з різними ребрами. Простий ланцюг - маршрут з різними вершинами (а значить, і ребрами)

Цикл - замкнутий ланцюг. Простий цикл - замкнутий маршрут, у которго всі n вершин різні і n> = 3. У позначеному графі G на рис.1 V1, V2, V4, V5, V3 - маршрут, який не є ланцюгом, а V1, V2, V5, V4, V2, V3 - ланцюг, де V1, V2, V5, V4 - проста ланцюг і V2, V4, V5, V2 - простий цикл. Позначимо через Gn граф, що складається з одного простого циклу з n вершинами, і через Pn простий ланцюг з n вершинами. Gn часто називають трикутником

Зв'язність Граф G називається зв'язаним, якщо будь-яка пара його вершин з'єднані простим ланцюгом. Максимальний зв'язний підграф графа G називається компонентою зв'язності або просто компонентою графа G. Таким чином, незв'язний граф має принаймні два компоненти. Граф на рис.2.9 має 10 компонент. Рис.2.9 Граф c 10 компонентами

Довжина маршруту дорівнює кількості ребер у ньому Кожне ребро рахується стільки разів, скільки воно зустрічаєтся в даному маршруті. Обхват графа g (G) - довжина найкоротшого простого циклу графа G (якщо він є). Оточення графа c (G) - довжина найдовшого простого циклу графа G. Ці поняття не визначені в разі, коли в G немає циклів. Відстанню d (u, v) між двома вершинами u та v графа G називається довжина найкоротшої простий ланцюга, що з'єднує їх. Якщо u і v не з'єднані, то вважаємо d (u, v) = нескінченність. У зв'язаному графі відстань є метрикою, тобто задовольняє наступним аксіомам: Аксіома метрики Для будь-яких трьох вершин u, v, w: 1) d (u, v)> = 0 і d (u, v) = 0 тоді і тільки тоді, коли u = v; 2) d (u, v) = d (v, u); 3) d (u, v) - | - d (v, w)> = d (u, w)

Найкоротша простий (uv)-ланцюг часто називається геодезичним. Діаметр d (G) зв'язного графа G - довжина найдовшої геодезичної. Граф G на рис.2.8 має: обхват g = 3, оточення c = 4, діаметр d = 2. Квадрат G2 графа G має ту ж безліч вершин, що і граф G, тобто V (G2) = V (G), і дві вершини u і v в G2 суміжні тоді і тільки тоді, коли d (u, v) <= 2 в G. Ступеня G3, G4 графа G визначаються аналогічно

Степень Ступінь вершини Vi в графі G - число ребер, інцидентних Vi. СТУПІНЬ = валентність = ЛОКАЛЬНА СТУПІНЬ Ступінь позначається di або deg Vi. Оскільки кожне ребро інцидентне двом вершинам, в суму ступенів вершин графа кожне ребро вносить двійку. Таким чином, ми приходимо до твердження, яке встановлено Ейлером і є історично першою теоремою теорії графів. ТЕОРЕМА Сума ступеня вершин графа G дорівнює подвоєному числу його ребер СЛІДСТВО 1 Сума ступеня вершин графа G дорівнює подвоєному числу його ребер В (p, q) графі 0 <= deg V <= p-1 для будь-якої вершини V. Мінімальний ступінь вершин графа G позначається через min deg G, максимальна - через max deg G

Якщо min deg G = max deg G = r, то всі вершини мають однаковий ступінь і такий граф G називається регулярним (або однорідним) ступеня r. У цьому випадку говорять про ступінь графа і пишуть deg G = r. Регулярний граф ступені 0 зовсім не має ребер. Якщо G - регулярний граф ступеня 1, то кожна його компонента містить точно 1 ребро; в регулярному графі ступеня 2 кожна компонента - цикл і, звичайно, назад. Кубічні графи - регулярні графи, які мають ступінь 3. На малюнку 2.10 показані два регулярних графа з 6 вершинами

СЛІДСТВО 2 Кожен кубічний граф має парне число вершин. Корисно дати назви вершин з малими ступенями. Вершина V називається ізольованою, якщо deg V = 0, і кінцевою (або висячою), якщо deg V =

2 способи задання графів Існують два основних способи завдання графів: геометричний; аналітичний. Аналітичний спосіб розділяється на два види: 1) Граф задається за допомогою двох множин: безліч вершин і безліч ребер, а також предиката, який вказує, які вершини з'єднані з якими ребрами. G (X; V) X {X1; X2;... Xn} V {V1; V2... Vm} P {Xi; Vt; Xj} Цей спосіб не є формалізованим. 2) Граф задається матрицею. Існує кілька матриць: матриця суміжності вершин; матриця суміжності ребер; матриця інцідентнсті та інші; матриця відстаней і інші

Література Басакер Р., Сааті Т. Кінцеві графи та мережі. М.: Наука, c. Бєлов В. В., Воробйов Є. М., Шаталов В. Є. Теорія графів - М.: Вища. школа, С Берж К. Теорія графів та її застосування. М.: ІЛ, c. Емелічев В. А., Мельников О. І., Сарванов В. І., Тишкевич Р. І. Лекції з теорії графів. М.: Наука, с. (Ізд.2, испр. М.: УРСС, с.) Зиков А. А. Основи теорії графів - М.: "Вузівська книга", С ISBN (М.: Наука, c.)ISBN