Поняття графа. Ребра і вершини.                                                      

 

       Графом в математиці називається картинка з крапочок, з'єднаних паличками (більш суворе визначення існує, але на практиці ніколи не потрібне). Ці крапочки називаються вершинами графа, а палички (вони можуть бути і кривими; деякі графи взагалі неможливо намалювати так, щоб усі палички були прямими) - ребрами графа. Дві вершини, з'єднані ребром, називаються сусідніми. Послідовність ребер, що з'єднують дві вершини, називається шляхом.

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

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

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

 

Для ізоморфізму орієнтованих графів потрібно також, щоб напрям ребер між вершинами з однаковими номерами було однаковим.

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

Ступені вершин, число ребер і парність.

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

У графі ступені вершин і кількість ребер пов'язані важливими співвідношеннями:

Задача 1. У державі 100 міст, з кожного виходить 2 дороги, окрім столиці, звідки виходить 5 доріг і міста Гірський, звідки виходить одна єдина дорога. Скільки всього доріг в державі? [20]

Розв’язання : Складемо кількості доріг, що виходять з усіх міст:

98 * 2 +5 +1 = 202. Це число - кількість кінців всіх доріг. Оскільки кожна дорога має 2 кінці, то кількість доріг буде вдвічі менше, а саме 101.

Аналогічними міркуваннями доводиться, що в будь-якому графі кількість ребер вдвічі менше суми ступенів усіх вершин.

Задача 2. На острів Коневец завезли 13 телефонів. Настоятель хоче організувати таку схему телефонного зв'язку, щоб з'єднати кожен телефон рівно з 7-ма іншими. Чи вдасться йому це?

Розв’язання : Порахуємо, скільки проводів потрібно, щоб здійснити таку схему. Кінців проводів буде 13 * 7 = 91, а самих проводів - удвічі менше, тобто ... 45,5 штук. Це означає, що така схема зв'язку неможлива.

Зауваження. Число непарних вершин будь-якого графа парне (саме ця властивість заважає побудувати мережу зв'язку в попередній задачі).

Доведення: Сума кількох цілих чисел парна тоді і тільки тоді, коли серед чисел парне число непарних. Застосуємо це до ступеня вершин: сума ступенів вершин парна тоді і тільки тоді, коли непарних вершин парне число. Але сума ступенів вершин завжди парна (вона рівно вдвічі більше числа ребер). Значить, і парних вершин завжди парне число.

Компоненти зв'язності.

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

Приклади:

Задача 3 Довести, що в державі (з задачі:У державі 100 міст, з кожного виходить 2 дороги, окрім столиці, звідки виходить 5 доріг і міста Гірський, звідки виходить одна єдина дорога. Скільки всього доріг в державі?) можна зі столиці доїхати (як-небудь, можливо, з декількома пересадками в різних містах), до міста Гірський.

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

Слід звернути увагу на запропонований прийом - розглянути компоненту зв'язності як окремий зв'язний граф і застосувати якесь твердження до цього графу

Задача 4.  На острові Коневец 13 привезених телефонів з'єднали між собою, причому з кожного телефону виходить не менш 6-ти проводів Довести, що а) з будь-якого телефону можна зв'язатися з будь-яким, б) це можна зробити, використовуючи не більше ніж 1 телефон в якості проміжної станції.

Розв’язання: Оскільки парність степенів вершин нам невідома, то відповідним твердженням ми користуватися не будемо. Зате, оскільки на степені вершин є оцінка знизу, то оцінимо знизу розмір компоненту зв'язності. У будь компоненті зв'язності є хоча б 1 вершина (1 телефон), а разом з нею - всі її сусіди (з'єднаний з ним проводами), що не менше 6 штук. Всього буде не менше 7 вершин.[18]

а) Якщо б у графі було хоча б 2 компоненти зв'язності, то було б не менше 2 * 7 = 14 вершин. А раз вершин всього лише 13, то компонента одна, тобто граф зв'язний.

б) Нам треба довести, що будь-які дві вершини - або сусіди, або мають загального сусіда. Це означає, що будь-які два "пучка" перетинаються (пучком буде називати безліч з однієї вершини - "центру пучка" - і всіх її сусідів). Але у попередньому  пункті ми оцінювали компоненти зв'язності саме пучком. Там ми довели, насправді, що в будь-якому пучку не менше 7 вершин, тому двох непересічних пучків у графі з 13 вершин бути не може.

Ейлерові графи.

Поняття ейлерового графа пов'язано зі наступними задачами: чи можна намалювати даний граф, не відриваючи олівець від паперу і проводячи кожне ребро рівно по разу? А чи можна так зробити, щоб врешті олівець повернувся в першу намальовану вершину? Виявляється, як встановив в XVIII столітті Леонард Ейлер, існує дуже простий критерій розв'язності цієї задачі.

А чи можна намалювати, не відриваючи олівця, два графа на малюнку внизу?

 

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

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

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

Насправді, разом з необхідністю критерію Ейлера ми довели ще ряд попутних фактів:

- Початок і кінець ейлерового шляху, якщо вони різні, завжди вершини непарного ступеня;

- тому в графі, де всі вершини парні, будь-який Ейлеровий шлях буде ейлеровим циклом;

- А в графі, де є 2 непарні вершини, тільки вони можуть бути початком і кінцем ейлерового шляху;

- Графи ж з одною непарною вершиною ми не розглядаємо, тому що їх немає в природі .