Неформально граф можна розглядати як безліч точок і ліній, що з'єднують ці точки, зі стрілками або без них.
Першою роботою теорії графів як математичної дисципліни вважають статтю Ейлера (1736), в якій розглядалося завдання про Кенінгсберзьких мостах. Ейлер показав, що не можна обійти сім міських мостів і повернутися до вихідної точки, пройшовши по кожному мосту рівно один раз. Наступний імпульс теорія графів отримала майже через 100 років з розвитком досліджень з електричних мереж, кристалографії, органічної хімії та інших наук.
З графами, сам того не помічаючи, ми стикаємося постійно. Наприклад, графом є схема ліній метрополітену. Крапками на ній представлені станції, а лініями – шляхи руху поїздів. Досліджуючи свій родовід і зводячи його до далекого предка, ми будуємо так зване генеалогічне дерево. І це дерево – граф.
Графи є зручним засобом опису зв'язків між об'єктами. Раніше ми вже використовували графи як спосіб наочного уявлення кінцевих бінарних відносин.
Але граф використовують не лише як ілюстрацію. Наприклад, розглядаючи граф, що зображує мережу доріг між населеними пунктами, можна визначити маршрут проїзду від пункту А до пункту Б. Якщо таких маршрутів виявиться кілька, хотілося б вибрати в певному сенсі оптимальний, наприклад, найкоротший або найбезпечніший. Щоб розв'язати завдання вибору потрібно проводити певні обчислення над графами. При вирішенні подібних завдань зручно використовувати техніку алгебри, та й саме поняття графа необхідно формалізувати.
Методи теорії графів широко застосовуються у дискретній математиці. Без них неможливо обійтися під час аналізу та синтезу різних дискретних перетворювачів: функціональних блоків комп'ютерів, комплексів програм тощо.
В даний час теорія графів охоплює великий матеріал та активно розвивається. При її викладі обмежимося лише частиною результатів та основний акцент зробимо на описі та обґрунтуванні деяких широко розповсюджених алгоритмів аналізу графів, що застосовуються в теорії формальних мов.
Основні визначення
Графи, як зазначалося в прикладах, є спосіб „візуалізації" зв'язків між певними об'єктами. Зв'язки ці можуть бути „спрямованими", як, наприклад, у генеалогічному дереві, або "неспрямованими" (мережа доріг з двостороннім рухом). Відповідно до цього в теорії графів виділяють два основні типи графів: орієнтовані (або спрямовані) та неорієнтовані.
Способи подання
Досі ми задавали орієнтовані та неорієнтовані графи, зображуючи їх за допомогою малюнків. Можна задати граф як пару множин, слідуючи визначенню, проте цей спосіб досить громіздкий і представляє, скоріше, теоретичний інтерес. Розвиток алгоритмічних підходів до аналізу властивостей графів потребує інших способів опису графів, придатніших для практичних обчислень, зокрема з використанням ЕОМ. Розглянемо три найбільш поширені способи представлення графів.
Дерева
Визначення 5.5. Неорієнтованим деревом називають зв'язковий та ациклічний неорієнтований граф. Визначення 5.6. Орієнтованим деревом називають безконтурний орієнтований граф, у якого півступінь заходу будь-якої вершини не більше 1 і існує одна вершина, звана коренем орієнтованого дерева, напівступінь заходу якої дорівнює 0.
Основне дерево найменшої ваги
Наступне завдання відоме теоретично графів під назвою задачі Штейнера: на площині задані пунктів; потрібно з'єднати їх відрізками прямих таким чином, щоб сумарна довжина відрізків була найменшою.
Методи систематичного обходу вершин графа
Важливими завданнями теорії графів є завдання глобального аналізу як неорієнтованих, і орієнтованих графів. До цих завдань належать, наприклад, завдання пошуку циклів або контурів, обчислення довжин шляхів між парами вершин, перерахування шляхів з тими чи іншими властивостями тощо. Глобальний аналіз графа слід відрізняти від локального, прикладом якого може бути завдання визначення множини попередників і наступників фіксованої вершини орієнтованого графа.
Завдання про шляхи у виважених орієнтованих графах
Ізоморфізм графів
Для орієнтованого графа (V, Е) безліч Е дуг можна розглядати як графік бінарного відношення безпосередньої досяжності, заданого на множині вершин. У неорієнтованому графі (V, Е) безліч Е ребер є безліччю невпорядкованих пар. Для кожної неупорядкованої пари (u, v) ∈ Е вважатимуться, що вершини u і v пов'язані симетричним бінарним ставленням р, тобто. (u, v) ∈ р та (v, u) ∈ р.
Топологічне сортування
Визначення 5.17. Орієнтованою мережею (або просто мережею) називають безконтурний орієнтований граф*. Оскільки мережа є безконтурним графом, можна показати, що існують вершини (вузли) мережі з нульовим півступенем результату, а також вершини (вузли) з нульовим півступенем заходу. Перші називають стоками чи виходами мережі, а другі - джерелами чи входами мережі.
Елементи цикломатики
Під час обговорення алгоритму пошуку у глибину в неорієнтованому графі розглядалося питання пошуку так званих фундаментальних циклів графа. При цьому під фундаментальним розумівся цикл, що містить в точності одне зворотне ребро, і між фундаментальними циклами і зворотними ребрами встановлювалася взаємно однозначна відповідність, фундаментальні цикли виникають щоразу, як тільки фіксовано довільне розбиття всіх ребер неорієнтованого графа на деревні (формують деякі графа) і зворотні, причому у випадку це розбиття може бути задано абсолютно незалежно від алгоритму пошуку в глибину. Пошук углиб є лише один із способів реалізації такого розбиття.
Теорія графів - розділ математики, що використовується в інформатиці та програмуванні, економіці, логістиці, хімії.
Що таке граф
Часто для опису будови систем використовують графічні схеми. Елементи в них зображують кружками, крапками, квадратами тощо, а зв'язки між елементами – лініями чи стрілками. У цьому ні те, як зображуються елементи, ні довжина чи форма ліній не важливі - має значення лише, які з'єднані. Отже, граф - це пара виду (A, M), де A - кінцева множина вершин, а M - множина ребер - ліній, що зв'язують деякі вершини.
Основні поняття теорії графів
У орієнтованого графа або орграфа (див. малюнок нижче) ребра орієнтовані, називаються дугами та зображуються стрілками. Дуга може бути позначена впорядкованою парою вершин, які вона пов'язує, – початковою та кінцевою.
У неорієнтованого графа (див. малюнок нижче) ребра зображуються лініями без орієнтації. Відповідно пара вершин, яку пов'язує ребро, є невпорядкованою. Обидві вершини є кінці ребра.
Якщо вершини a і b - кінці ребра (або початок і кінець дуги) графа, то кажуть, що вершини a і b інцидентні цьому ребру (дузі), також ребро (дуга) інцидентно вершинам a і b. Якщо вершини a і b - кінці ребра, всі вони (a і b) називаються суміжними.
Найчастіше розглядають графи, ребра яких мають один тип – є орієнтованими чи ні.
Якщо ребра має однакові початок і кінець, їх називають кратними ребрами, а граф, у якому присутні, називається мультиграфом.
Теорія графів також використовує поняття «петля» - ребро, що виходить і заходить в ту саму вершину. Граф, у якому є петлі, називається псевдографом.
Найчастіше зустрічаються неорієнтовані графи, які не мають кратних ребер і немає петель. Такі графи називаються звичайними. Вони не мають кратних ребер, тому можна ототожнити ребро та пару вершин.
Кожна вершина орграфа характеризується:
- Напівступенем результату. Це кількість дуг, що виходять із неї.
- Напівступенем заходу. Це кількість дуг, які входять у цю вершину.
Сума напівступеня заходу орграфа, а також сума напівступеня результату рівні загальної кількості дуг графа.
У неорієнтованого графа кожна вершина характеризується ступенем вершини. Так називається кількість ребер, які інцидентні на вершині. Загальна сума ступенів вершин графа є кількість ребер, помножена на два: кожне ребро даватиме внесок, який дорівнює двом.
Вершина зі ступенем 0 називається ізольованою.
Висячою вершиною є вершина зі ступенем 1.
Теорія графів називає порожнім графом такий, у якому немає жодного ребра. Повний граф - це звичайний граф, у якому суміжні будь-які 2 вершини.
Зважені графи - це графи, вершинам або ребрам (дугам) яких або вершинам, і ребрам (дугам) відразу, приписуються деякі числа. Вони називаються вагами. На другому малюнку показаний неорієнтований граф, ребра якого зважені.
Графи: ізоморфізм
Поняття ізоморфізму використовується в математиці. Зокрема, теорія графів визначає його так: два графи U і V ізоморфні, якщо в цих графах існує бієкція між множинами їх вершин: кожні 2 вершини у графі U з'єднані ребром у тому і тільки тому випадку, якщо у графі V пов'язані ребром ті ж самі вершини (які можуть інакше називатися). На малюнку нижче показані два ізоморфні графи, в яких між вершинами, забарвленими в однакові кольори і в першому, і в другому графі, існує вищеописана біекція.
Шляхи та цикли
Шляхом у неорієнтованому чи орієнтованому графі є послідовність ребер, де кожне наступне починається у вершині, у якій закінчується попереднє. Простий шлях - такий, у якому всі вершини, виключаючи, можливо, початкову і кінцеву, і ребра різні. Циклом в орграфі називається шлях, у якого збігаються початкова і кінцева вершини і включає не менше одного ребра. Циклом у неорієнтованому графі є шлях, який містить щонайменше трьох різних ребер. На другому малюнку циклом є, наприклад, шлях (3, 1), (6, 3), (1, 6).
Теорія графів у програмуванні використовується для побудови граф-схем алгоритмів.
Книга К.Бержа – перша з теорії графів російською мовою. Тим часом останніми роками інтерес до теорії різко посилився як з боку математиків, так і представників різних дисциплін. Це тим, що методи теорії графів успішно вирішують численні завдання теорії електричних ланцюгів, теорії транспортних ланцюгів, теорії інформації, кібернетики та інших.
У книзі Бержа теорія графів викладається послідовно, починаючи з основ. Передбачається, що читач має дуже скромні математичні знання, хоча і має деяку математичну культуру. У текст включені численні, часто кумедні, приклади. Книжку можна використовувати для початкового вивчення теорії графів. Математики-професіонали також знайдуть у ній багато цікавого.
Алгорифм для безпосереднього виявлення ейлерового циклу.
[Флерн (Fleury)]. Розглянемо зв'язковий мультиграф G, всі вершини якого мають парний ступінь, і постараємося намалювати його одним розчерком, не вдаючись у процесі побудови виправлень вже накресленої частини траєкторії. Достатньо дотримуватися наступного правила:
1 Виходимо з довільної вершини а; кожне пройдене ребро закреслюємо.
2 Ніколи не йдемо по такому ребру і, яке в даний момент є перешийком (тобто при видаленні якого граф, утворений незакресленими ребрами, розпадається на дві компоненти зв'язності, що мають хоча б по одному ребру),
Дотримуючись цього правила, ми завжди знаходимося у сприятливому становищі, тому що коли ми знаходимося в х = а, граф (з незакреслених ребер) має дві вершини непарного ступеня: х і а; якщо відкинути ізольовані вершини, то залишиться зв'язковий граф, який через теорему 1 має ейлерову ланцюг, що починається в х.
Зміст
Вступ
Глава 1. Основні визначення
Множини та багатозначні відображення
Граф. Шляхи та контури
Ланцюги та цикли
Глава 2. Попереднє вивчення квазіупорядкованості
Квазіпорядок, що визначається графом
Індуктивний граф та бази
Глава 3. Порядкова функція та функція
Гранді для нескінченного графа
Загальні міркування щодо нескінченних графів
Порядкова функція
Функції гранді
Операції над графами
Глава 4. Основні числа теорії графів
Цикломатичне число
Хроматичне число
Число внутрішньої стійкості
Число зовнішньої стійкості
Розділ 5. Ядра графа
Теореми існування та єдиності
Додаток до функцій Гранді
Розділ 6. Ігри на графі
Гра Нім
Загальне визначення гри (з повною інформацією)
Стратегії
Глава 7. Завдання про найкоротший шлях
Процеси за етапами Деякі узагальнення
Глава 8. Транспортні мережі
Завдання про найбільший потік Завдання про найменший потік
Завдання про потік, сумісний з безліччю значень
Нескінченні транспортні мережі
Глава 9. Теорема про напівступеня
Пів ступеня результату та заходу
Глава 10. Паросполучення простого графа
Завдання про найбільше паросомовчання
Дефіцит простого графа
Угорський алгоритм
Узагальнення на нескінченний випадок
Додаток до теорії матриць
Розділ 11. Фактори
Гамільтонові шляхи та гамільтонові контури
Знаходження фактора
Знаходження часткового графа із заданими напівступенями
Розділ 12. Центри графа
Центри
Радіус
Розділ 13. Діаметр сильно зв'язного графа
Загальні властивості сильно зв'язкових графів без петель
Діаметр
Глава 14. Матриця суміжності графа
Застосування звичайних матричних операцій
Завдання на підрахунок
Завдання про лідера
Застосування булевих операцій
Розділ 15. Матриці інцидентів
Цілком унімодулярні матриці
Цілком унімодулярні системи
Цикломатичні матриці
Глава 16. Дерева та прадерева
Дерева
Аналітичне дослідження
Прадерева
Розділ 17. Завдання Ейлера
Ейлерові цикли Ейлерові контури
Глава 18. Паросопоєднання довільного графа
Теорія ланцюгів, що чергуються.
Знаходження часткового графа із заданими ступенями вершин
Досконалий паросполучення
Додаток до внутрішньої стійкості
Глава 19. Фактороїди
Гамільтонові цикли та фактороїди
Необхідна та достатня умова існування фактороїду
Глава 20. Зв'язок графа
Точки зчленування
Графи без зчленувань
h-зв'язкові графи
Розділ 21. Плоскі графи
Основні властивості
Узагальнення
Додавання
I. Off загальної теорії, ігор
ІІ. Про транспортні завдання
ІІІ. Про використання, поняття потенціалу у транспортних мережах
IV. Невирішені завдання та недоведені припущення
V. Про деякі основні принципи підрахунку (Ж. Рига)
VI. Доповнення до російського перекладу (А.А. Зиков та Г.І. Кожухін)
Література
Теорія графів та книга К. Бержа (післямова до російського перекладу)
Вказівник символів
Іменний покажчик
Предметний покажчик.
Безкоштовно скачати електронну книгу у зручному форматі, дивитися та читати:
Скачати книгу Теорія графів та її застосування, Берж К. - fileskachat.com, швидке та безкоштовне скачування.
Теорія графів – це розділ дискретної математики, вивчає об'єкти, які у вигляді окремих елементів (вершин) і зв'язків з-поміж них (дуг, ребер).
Теорія графів бере початок з розв'язання задачі про кенігсберзькі мости в 1736 знаменитим математиком Леонардом Ейлером(1707-1783: народився у Швейцарії, жив та працював у Росії).
Завдання про кенігсберзькі мости.
У прусському містечку Кенігсберг на річці Прега сім мостів. Чи можна знайти маршрут прогулянки, який проходить рівно один раз по кожному з мостів і починається і закінчується в одному місці?
Граф, в якому знайдеться маршрут, що починається і закінчується в одній вершині, і проходить по всіх ребрах графа рівно один раз, називаєтьсяЕйлеровим графом.
Послідовність вершин (можливо з повторенням), якими проходить шуканий маршрут, як і сам маршрут, називаєтьсяЕйлеровим циклом .
Завдання про три будинки та три колодязі.
Є три будинки та три колодязі, якимось чином розташовані на площині. Провести від кожного будинку до кожної криниці стежку так, щоб стежки не перетиналися. Це завдання було вирішено (показано, що рішення не існує) Куратовським (1896 – 1979) у 1930 році.
Завдання про чотири фарби. Розбиття площини на області, що не перетинаються, називається карткою. Області картки називаються сусідніми, якщо вони мають спільний кордон. Завдання полягає у розмальовуванні карти таким чином, щоб жодні дві сусідні області не були зафарбовані одним кольором. З кінця ХІХ століття відома гіпотеза, що цього досить чотирьох фарб. Гіпотезу не доведено досі.
Суть опублікованого рішення полягає в тому, щоб перебрати велике, але кінцеве число (близько 2000) типів потенційних контрприкладів до теореми про чотири фарби і показати, що жоден випадок контрприкладом не є. Цей перебір було виконано програмою приблизно за тисячу годин роботи суперкомп'ютера.
Перевірити «вручну» отримане рішення неможливо – обсяг перебору виходить за межі людських можливостей. Багато математиків порушують питання: чи можна вважати такий «програмний доказ» дійсним доказом? Адже у програмі можуть бути помилки.
Таким чином, залишається сподіватися на програмістську кваліфікацію авторів і вірити, що вони зробили правильно.
Визначення 7.1. Графом G= G(V, E) називається сукупність двох кінцевих множин: V – званого безліччю вершинта множини E пар елементів з V, тобто. EIV'V, званого безліччю реберякщо пари невпорядковані, або безліччю дугякщо пари впорядковані.
У першому випадку граф G(V, E) називається неорієнтованим, у другому – орієнтованим.
ПРИКЛАД. Граф з безліччю вершин V = (а, b, с) і безліччю ребер Е = ((а, b), (b, с))
ПРИКЛАД. Граф, у якого V = (a, b, c, d, e) та Е = ((а, b), (а, е), (b, е), (b, d), (b, с) , (С, d)),
Якщо e=(v 1 ,v 2), еÎЕ, то кажуть, що ребро е з'єднуєвершини v 1 та v 2 .
Дві вершини v 1 ,v 2 називаються суміжними, якщо існує ребро, що з'єднує їх. У цій ситуації кожна з вершин називається інцидентної відповідному ребру .
Два різних ребра суміжніякщо вони мають загальну вершину. У цій ситуації кожне з ребер називається інцидентним відповідної вершині .
Число вершин графа Gпозначимо v, а число ребер - e:
.
Геометричне представлення графів таке:
1) вершина графа – точка у просторі (на площині);
2) ребро неорієнтованого графа – відрізок;
3) дуга орієнтованого графа – спрямований відрізок.
Визначення 7.2.Якщо ребері e=(v 1 ,v 2) має місце v 1 =v 2 , то ребро е називається петлею. Якщо у графі допускається наявність петель, то він називається графом із петлями або псевдографом .
Якщо у графі допускається наявність більше одного ребра між двома вершинами, він називається мультиграфом .
Якщо кожна вершина графа та (або) ребра позначена, то такий граф називається поміченим (або навантаженим ). Як позначки зазвичай використовуються літери або цілі числа.
Визначення 7.3.Граф G (V , E ) називається підграфом (або частиною ) графа G(V,E), якщо V V, E E. Якщо V = V, то G називається остовним підграфом G.
приклад 7 . 1 . Дано неорієнтований граф.
Визначення 7.4.Граф називається повним , якщо будь-які дві його вершини з'єднані рубом. Повний граф з nвершинами позначається через K n .
Графи К 2 , К 3, До 4 і К 5 .
Визначення 7.5.Граф G=G(V, E) називається дводольним , якщо Vможна уявити як об'єднання непересічних множин, скажімо V=ABтак що кожне ребро має вигляд ( v i , v j), де v i Aі v j B.
Кожне ребро пов'язує вершину з А з вершиною В, але ніякі дві вершини А або дві вершини В не є пов'язаними.
Дводольний граф називається повним дводольним графом K m , n, якщо Aмістить mвершин, Bмістить nвершин і для кожного v i A, v j Bмаємо ( v i , v j)E.
Таким чином, для кожного v i A, і v j Bє їхнє ребро.
K 12 K 23 K 22 K 33
приклад 7 . 2 . Побудувати повний дводольний граф K 2,4 та повний граф K 4 .
Граф одиничногоn-мірного кубаУ n .
Вершини графа – n-мірні двійкові набори. Ребра з'єднують вершини, що відрізняються однією координатою.
Приклад: 
Тема графів – це цікава, корисна та лякаюча тема. Теорія графів - "Жах студента". Алгоритми на графах — приголомшливий розум людей, які їх відкрили.
Що таке граф? Щоб відповісти на це запитання своїм читачам, я описуватиму тему трохи по-своєму.
Граф – це безліч об'єктів.
Здебільшого це однотипні об'єкти. (Багато міст або безліч будинків, або безліч людей, або безліч чогось ще однотипного)
Щоб вирішувати завдання з такою множиною, потрібно кожен об'єкт із цієї множини позначити як щось. Загальноприйнято це щось називати вершинами графа.
Описувати графи та основні визначення зручно малюнками, тому для читання цієї сторінки малюнки мають бути включені.
Як я й писав раніше — граф це якась безліч об'єктів. Ці об'єкти зазвичай однотипні. Найпростіше наводити приклад на містах. Кожен із нас знає, що таке місто та що таке дорога. Кожен із нас знає, що до міста можуть бути дорогі, а можуть і не бути. Загалом, багато об'єктів можна охарактеризувати як граф.
Якщо говорити про граф як міста, то між містами можуть бути прокладені дороги, а може бути десь зруйнована, не побудована, або ж місто взагалі знаходиться на острові, мосту немає, а цікавлять тільки дороги з твердим покриттям. Незважаючи на те, що дороги до такого міста немає, це місто може бути включене до безлічі об'єктів, що аналізуються, і всі об'єкти разом узяті становлять сукупність об'єктів або простіше кажучи — граф.
Напевно, ви читали підручники і бачили такий запис G(V,E) або щось схоже. Так ось, V — це якийсь один об'єкт із безлічі об'єктів. У нашому випадку безліч об'єктів — це міста, отже, V — це якесь певне місто. Так як об'єкти не обов'язково міста, а слово об'єкт може заплутати, то такий об'єкт із множини можна називати точкою, пунктом, якось ще, але найчастіше його називають вершиною графа і позначають буквою V.
У програмуванні це зазвичай стовпець або рядок двовимірного масиву, де масив називається або матрицею суміжності або матрицею інцендентності.
У літературі, в інтернеті і взагалі скрізь, де щось написано про графи, ви зустрічатимете такі поняття, як дуги та ребра. На цьому малюнку зображено ребра графа. Тобто. це три ребра Е1, Е2 та Е3.
Дуга і ребро відрізняються тим, що ребро це такий двонаправлений зв'язок. Захотів, пішов до сусіда, схотів, повернувся від сусіда. Якщо не дуже зрозуміло, то можна уявити будинок, аеродром, літак, що летить, і парашутиста. Парашутист може піти зі свого будинку на аеродром, але коли прийшов на аеродром, згадати, що свій щасливий парашут забув удома, потім повернутись додому, взяти парашут. — Така дорога, якою можна гуляти туди й назад, називається рубом.
Якщо парашутист перебуває в літаку і стрибає з літака, але парашутист забув у літаку надіти свій щасливий парашут, то чи зможе парашутист забрати, що забув? Такий шлях, що йде лише в один бік, називається дугою. Зазвичай кажуть, що ребро з'єднує дві вершини, а дуга йде з однієї вершини до іншої.
На цьому малюнку у графа лише дуги. Дуги на графі позначають стрілками, тому що так ясно доступний напрямок. Якщо граф складається з одних таких дуг, такий граф називається орієнтованим.
 |
Ви часто зустрічатимете поняття суміжності та інцендентності. На малюнку червоним кольором відмічені два ребра, які йдуть в одну точку. Такі ребра, як і вищеописані вершини, також називаються суміжними. |
Багато чого не описано, але ця частина інформації може бути комусь допоможе.