Теорія графів - виникло в кінці XVIII столітті і в даний час перетворилася в досить потужний і безперервно розвивається математичний інструмент.
У багатьох випадках життя стара звичка штовхає нас малювати на папері точки, що зображують людей, населені пункти, хімічні речовини і т. Д. І з'єднувати ці точки лініями або стрілками, які дають зрозуміти деякі відносини. Такі схеми зустрічаються всюди під різними назвами: соціограма (в психології), симплекси (в топології), електричні ланцюги (у фізиці), діаграми організації (в економіці), мережі комунікацій, генеалогічні дерева і т.д. Д.Кёніг, без сумніву перший, запропонував називати такі схеми "графами" і систематично вивчати їх властивості.
Перше з основних понять теорії графів - це поняття вершини. В теорії графів воно приймається в якості первинного і не визначається. Його неважко уявити собі на власному інтуїтивному рівні. Зазвичай вершини графа наочно зображуються у вигляді кіл, прямокутників іншими фігурами (рис.1). Хоча б одна вершина повинна обов'язково бути присутнім в кожному графі.
Інша основне поняття теорії графів - дуги. Зазвичай дуги являють собою відрізки прямих або кривих, що з'єднують вершини. Кожен з двох кінців дуги повинен збігатися з якою-небудь вершиною. Випадок, коли обидва кінці дуги збігаються з однією і тією ж вершиною, не виключається. Наприклад, на рис.2 - допустимі зображення дуг, а на рис.3 - неприпустимі:
В теорії графів використовуються дуги двох типів - ненаправленої або спрямованими (орієнтованими). Граф, що містить тільки орієнтовані дуги, називається орієнтованим графом або Орграф.
Дуги можуть бути односпрямованим, при цьому кожна дуга має тільки один напрямок, або двонаправленими.
У більшості застосувань можна без втрати сенсу замінити ненаправлену дугу на двосторонню, а двосторонню - на дві односпрямованих дуги. Наприклад так, як показано на рис. 4.
Як правило, граф або відразу будується таким чином, щоб всі дуги мали однакову характеристику спрямованості (наприклад, все - односпрямовані), або приводиться до такого виду шляхом перетворень. Якщо дуга AB- спрямована, то це означає, що з двох її кінців один (A) вважається початком, а другий (B) - кінцем. У цьому випадку говорять, що початок дуги AB є вершина A, а кінець - вершина B, якщо дуга спрямована від A до B, або що - дуга AB виходить з вершини A і входить B (рис. 5).
Дві вершини графа, з'єднані будь-якої дугою (іноді, незалежно від орієнтації дуги) називають суміжними вершинами.
Важливим поняттям при дослідженні графів є поняття шляху. Шлях A1, A2. An визначається як кінцева послідовність (кортеж) вершин A1, A2. An і дуг A1, 2, A2, 3. An-1, n послідовно з'єднують ці вершини.
Важливим поняттям в теорії графів є поняття зв'язності. Якщо для будь-яких двох вершин графа існує хоча б один з'єднує їх шлях - граф називається зв'язковим.
Наприклад, якщо зобразити у вигляді графа систему кровообігу людини, де вершини відповідають внутрішнім органам, а дуги - кровоносних капілярах, то такий граф, очевидно, є зв'язковим. Чи можна стверджувати, що система кровообігу двох довільних людей є незв'язним графом? Очевидно, немає, оскільки в природі спостерігаються т. Н. "сіамські близнюки".
Можливості підключення може бути не тільки якісною характеристикою графа (зв'язний / незв'язних), але і кількісної.
Граф називається K-зв'язковим, якщо кожна його вершина пов'язана з K інших вершин. Іноді говорять про слабо-і сильносвязанних графах. Ці поняття є суб'єктивними. Дослідник називає граф Сільносвязанная якщо для кожної його вершини кількість суміжних вершин, на думку дослідника, велике. Іноді зв'язність визначають як характеристику не кожній, а однією (довільної) вершини. Тоді з'являються визначення типу: граф називається K-зв'язковим, якщо хоча б одна його вершина пов'язана з K інших вершин.
Наприклад, дитячий малюнок людини (рис. 6) являє собою граф з максимальною связностью рівній 4.
Ще одна характеристика графа, досліджувана в ряді завдань, часто називається потужністю графа. Ця характеристика визначається як кількість дуг, що пов'язують дві вершини. При цьому дуги, мають зустрічний напрямок, часто розглядаються окремо.
Наприклад, якщо вершини графа уявляю собою вузли обробки інформації, а дуги - односпрямовані канали передачі інформації між ними, то надійність системи визначається не сумарною кількістю каналів, а найменшою кількістю каналів в будь-якому напрямку.
Потужність, як і зв'язність, може визначатися як для кожної пари вершин графа, так і для деякої (довільної) пари.
Істотна характеристика графа - його розмірність. Під цим поняттям зазвичай розуміють кількість вершин і дуг, що існують в графі. Іноді ця величина визначається як сума кількостей елементів обох видів, іноді - як твір, іноді - як кількість елементів тільки одного (того чи іншого) виду.
Об'єкти, що моделюються графами, мають досить різноманітну природу. Прагнення відбити цю специфіку призвело до опису великої кількості різновидів графів. Процес цей триває і в даний час. Багато дослідників для своїх конкретних цілей вводять нові різновиди і виконують їх математичне дослідження з більшим чи меншим успіхом.
В основі всього цього різноманіття лежать кілька досить простих ідей, про які ми тут і будемо говорити.
Забарвлення графів - вельми популярний спосіб модифікації графів.
Цей прийом дозволяє і підвищити наочність моделі і збільшити математичну навантаженість. Способи введення забарвлення можуть бути різними. З тих чи інших правил фарбуються як дуги, так і вершини. Забарвлення може бути одноразово визначена або змінюватися з плином часу (тобто при придбанні графом будь-яких властивостей); кольори можна перетворювати з тих чи інших правил, і т.д.
Наприклад, нехай граф являє собою модель кровообігу людини, де вершини відповідають внутрішнім органам, а дуги - кровоносних капілярах. Забарвимо артерії в червоний колір, а вени - в синій. Тоді очевидно справедливість наступного твердження - в розглянутому графі (рис. 8) існують, і при цьому тільки дві, вершини, що мають вихідні червоні дуги (на малюнку червоний колір зображений жирно).
Іноді елементи об'єкта, що моделюються вершинами, мають істотно різний характер. Або до реально існуючих в об'єкті елементів в процесі формалізації виявляється за потрібне додати деякі фіктивні елементи. У цьому, і деяких інших випадках, вершини графа природно розділити на класи (частки). Граф, що містить вершини двох типів, називають дводольним і т.д. При цьому в число обмежень графа вносяться правила, що стосуються взаємин вершин різних типів. Наприклад: "не існує дуги, яка б поєднувала вершини одного типу". Одна з різновидів графів такого роду називається "мережа Петрі" (рис. 9) і має досить широке поширення. Більш докладно мережі Петрі будуть розглянуті в наступній статті цього циклу.
Поняття дольності може бути застосовано не тільки до вершин, а й до дуг.
Використовуючи графи можна вирішувати завдання.