Теорія графів. Частина 1 Введення та класифікація графів

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

Вступ

Спершу під землею міста Москви нічого не було. Потім було збудовано першу станцію метро, ​​а потім і другу і третю. Утворилося безліч станцій метро. На карту було занесено безліч точок. Пізніше між станціями почали прокладати шляхи лінії. І з'єдналася станція метро А зі станцією метро Б. Всі інші станції також стали з'єднуються одна з одною і на карті з'явилося безліч ліній. У результаті ми маємо Московський метрополітен дуже гарний, я там перевіряв.

Схема Московського метро

Подивіться якась краса. У нас є безліч точок (які називаються вершинами чи вузлами), а також безліч ліній (звані ребрами чи дугами). Позначимо безліч вершин буквою V від англійського vertex-вершина і безліч ребер позначимо E від англійського edge-ребро. Граф у формулах називають літерою G. Усі вершини обов'язково мають бути ідентифіковано.

Зазначу, що вершин позначається буквою n:

Число ребер позначається буквою m:

Таким чином граф задається та позначається парою V,E:

Граф - це сукупність кількох множин. Кінцевого є і нескінченні, проте ми їх поки не розглядаємо непустої множини V і множини E заданої невпорядкованими парами множини V.

Також визначення графа розповідається у цій статті на Хабрі (https://habr.com/ua/post/65367/)

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

Розберемо визначення графа докладніше. Чи може G бути порожнім безліч E? Та без проблем! Такий граф називатиметься нульовим, а вершини в ньому називатимуться ізольованими.

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

Безліч E задається парою невпорядкованих вершин множини V.

Приклад: Нехай безліч V =. Тоді безліч E =

Граф виглядатиме так:

Висячої вершиною називається вершина, яка з'єднана тільки з однією сусідньою вершиною. У нашому випадку висячою вершиною буде вершина 5, так як вона з'єднана тільки з вершиною 1.

ступенем вершини - є кількість ребер, що виходять з вершини і входять до неї. Дане визначення правильне для орієнтованих графів див. класифікацію графів. Для неорієнтованих графів вихідний ступінь дорівнює вхідній. Ступенем вершини 1 буде число 4. Так як вершина 1 з'єднана з вершиною 2, 3, 4, 5.

Ступінь записують, як:

Максимальний ступінь, тобто скільки ступенів взагалі присутні у графі позначаються, як:

Формула суми ступенів для G = V,E виглядає так:

Тобто сума ступенів всіх вершин v графа дорівнює подвоєній кількості його ребер E. Вважаємо кількість ступенів у нашому прикладі. Від цього нікуди не дінешся. Я нарахував 12. А тепер рахуємо, скільки у нас ребер. Їх 6! Помножуємо на 2 та отримуємо 12.Збіг? Не думаю!

А давайте уявимо наш граф в іншому вигляді, але зі збереженням цих пар. G тепер має такий вигляд:

Зауважте я не змінив пари між собою. Вершина 4 також з'єднується з вершиною 3, а у вершини 1 ступінь також залишилася 4. Так чому граф має зовсім інший вигляд і чи це законно?

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

Класифікації графів

• Першою ознакою класифікації є відсутність чи наявність орієнтації у ребер. Ребро є неорієнтованим якщо він не має поняття початку чи кінця. Тобто обидва його кінці рівноправні. Такий граф називається неорієнтованим, звичайним або неографом.

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

Також існує граф зі змішаними ребрами. Це коли у графі присутні як орієнтовані ребра, так і неорієнтовані.

• Другою ознакою є відсутність чи наявність кратних ребер. Кратні ребра - це ребра, які зустрічаються між двома вершинами відразу кілька разів. У прикладі нижче бачимо, що вершина a з'єднана з вершиною c кілька разів.Те саме відбувається і a c b. Такий граф називається мультиграфом.

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

Висновок

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

Графи та способи їх подання

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

Вступ

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

Значно зросла популярність теорії графів – гілки дискретної математики.Графи зустрічаються у багатьох областях під різними назвами: "структури" у цивільному будівництві, "мережі" - в електроніці, "соціограми" - в соціології та економіці, "молекулярні структури" - у хімії, "дорожні карти", електричні або газові розподільчі мережі і т.д. буд.

Народившись при вирішенні головоломок та ігор, таких, наприклад, як завдання про кенігсберзькі мости і гра Гамільтона, теорія графів стала потужним засобом дослідження та вирішення багатьох завдань, що виникають при вивченні великих і складних систем. Для фахівців з обчислювальної техніки, інформаційних систем та систем цифрового зв'язку теорія графів – це зручна мова вираження понять із цієї галузі; Багато результатів теорії графів мають безпосередній зв'язок із завданнями, з якими їм доводиться стикатися. Графічна інтерпретація різних моделей графів дано на рис. 1.1 Так як орієнтованих графів можна уявити будь-яку логічну чи функціонально - логічну схему ( рис. 1.1,а). На таких графових моделях можна, наприклад, оцінити швидкодію схеми. Блок-схема алгоритму може бути представлена ​​імовірнісним графом (рис. 1.1, б), що дозволяє оцінити часові характеристики алгоритму, витрати процесорного часу, трудомісткість та інші. Графом типу "дерево" можна відобразити практично будь-яку структуру організації або підприємства (рис. 1.1, в).

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

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