Відстані в графах
Нехай G =
Довжина найкоротшого (Vi, Vj) -Маршрут називається відстанню між вершинами Vi і Vj і позначається через # 63; (Vi, Vj).
покладемо # 63; (Vi, Vj) = 0. Очевидно, що введене таким чином відстань задовольняє наступним аксіомам метрики:
1) # 63; (Vi, Vj) # 63; 0;
2) # 63; (Vi, Vj) = 0 # 45; Vi = Vj
3) # 63; (Vi, Vj) = # 63; (Vi, Vj) - симетричність
4) # 63; (Vi, Vj) # 63; # 63; (Vi, Vj) + # 63; (Vj, Vк) - нерівність трикутника.
Якщо V =, то матриця Р = (рi, j) = # 63; (Vi, Vj), називається матрицею відстаней (де матриця Р симетрична).
Для фіксованої вершини V величина Е (v) = мах <? (Vi, Vj) | Vj є V> називається ексцентриситетом вершини V. Таким чином, ексцентриситет вершини дорівнює відстані від даної вершини до найбільш віддаленої від неї.
Якщо Р-матриця відстаней, то ексцентриситет Е (Vi) дорівнює найбільшому з числі, що стоять в i-му рядку.
Максимальний серед усіх ексцентриситетів вершин називається діаметром графа G і позначається через d (G). d (G) = vf [. Вершина V називається периферійної, якщо Е (v) = d (G).
Розглянемо приклад. Знайдемо діаметр графа G, зображений на рис.18. Матриця відстаней Р має вигляд:
Звідси Е (1) = 3, Е (2) = 2, Е (3) = 3, Е (4) = 2, Е (5) = 2 і, отже, d (G) = 3. Вершини 1 і 3 є периферійними.
Мінімальний з ексцентриситетом графа G називається його радіусом і позначається через r (G). r (G) = min.
Вершина V називається центральної, якщо Е (v) = r (G).
Безліч всіх центральних вершин графа називається його центром.
Розглянемо відповідний приклад. Радіус графа, показаного на рис.18, дорівнює 2, а його центром є безліч.
Завдання знаходження центральних вершин виникає в практичній діяльності людей. Нехай, наприклад, граф являє собою мережу доріг, тобто вершини відповідають населеним пунктам, а ребра - дорогам між ними. Потрібно оптимально розмістити лікарні, пункти обслуговування і т.п. У подібних ситуаціях оптимізація полягає в мінімізації відстані від місця обслуговування до найбільш віддаленого населеного пункту. Отже, місцями розміщення повинні бути центральні вершини графа. Реальні завдання відрізняються від цієї ідеальної теми, що доводиться враховувати і інші обставини - відстані між населеними пунктами, вартість, час проїзду і т.д.
Дерево - один з найбільш часто зустрічаються в теорії графів понять (рис.19).
Ясно, що «особливе місце» в дереві займають не тільки висячі вершини. Виділяються в цих деревах і вершини, відмічені подвійним кружком. Такі вершини називають кореневими.
Кореневу вершину неважко також виділити у дерев на малюнках 20, 21, 22.
У першому випадку кореневої вершиною є єдина вершина графа А, у другому - вершина С, в третьому (таке дерево, все вершини якого, крім однієї, висячі, називають «зіркою») - вершина А. Але які вершини вважати кореневими в графах, які зображені на малюнках 23, 24 і 25?
Природно вважати, що всі ці три дерева мають по дві кореневі вершини. У дерева на малюнку 23 - це А і В, у дерева на малюнку 24 - це С і Д, у дерева на малюнку 25 - це А і В.
Відстанню d (Vi, Vj) між вершинами Vi і Vj графа G називають довжину найкоротшого шляху, їх з'єднує. (Якщо граф G-дерево, то шлях з'єднує вершини Vi і Vj, єдиний).
Підрахуємо для кожної вершини дерева, зображеного на малюнку 26, найбільше з відстаней до всіх інших його вершин і запишемо ці числа на малюнку біля вершин (рис.27).
Найбільше з таких чисел називають діаметром графа (в даному випадку дерева), найменше - радіусом графа.
Вершини дерева, для яких максимальне з відстаней до інших вершин дорівнює радіусу, називаються кореневими. Для дерева, зображеного на малюнку 26, діаметр дорівнює 5, а радіус дорівнює 3; кореневі вершини - А і В.
Завдання. Підрахуйте діаметр і радіус графа, зображеного на малюнку:
Вирішимо ще одне завдання з хімії: «Насиченим вуглеводнем називається з'єднання вуглецю С, що має валентність 4 і водню Н, має валентність 1, в якому при заданому числі атомів вуглецю міститься найбільша кількість атомів водню. Знайдіть формулу насиченого вуглеводню, що містить n атомів вуглецю ».
Розглянемо граф, в якому вершинами є атоми, а ребрами - відповідні валентні зв'язки між ними. Покажемо від противного, що в графі не існує циклу, тобто можливості, переходячи по ребрах графа з вершини в вершину, повернутися у вихідну вершину. Якщо цикл є, то повинен бути складений з атомів вуглецю, оскільки водень має валентність 1 і може з'єднуватися тільки з одним атомом. У разі існування циклу розірвемо зв'язок між двома атомами вуглецю і приєднаємо до кожного з них ще по одному водню. Число атомів водню збільшиться, значить, вихідний граф описується не молекулу насиченого вуглеводню.
У побудованому графі можна перейти по ребрах від будь-якої вершини до будь-якої іншої, і в ньому немає циклів. Такий граф називається деревом. Нехай молекула містить n атомів вуглецю і m атомів водню, тоді граф буде містити n + m вершин. Далі, при вирішенні завдання скористаємося легко доводимо співвідношенням: в дереві число ребер на одиницю менше числа вершин. Отже, в графі n + m - 1 ребер. З вершин графа, що позначають атоми вуглецю, виходить по 4 ребра, а з вершин, що позначають атоми водню, - одне. Використовуючи простий факт, що сума ступенів вершин, тобто сума числа ребер, можна написати співвідношення: 4n + m = 2 (n + m - 1). Звідси отримуємо, що m = 2n + 2. Отже, формула насиченого вуглеводню, що має n атомів вуглецю: Сn H2n + n.
Тобто можна отримати формулу речовини за допомогою математики, використовуючи тільки визначення і не проводячи хімічних дослідів.
До числа граничних (які не мають циклу) вуглеводнів відноситься, наприклад пентан С5Н12. Його структурна формула зображена на малюнку 28. Цією формулою можна поставити у взаємно однозначну відповідність однокореневих дерево (рис. 29), що показує взаємне розташування тільки атомів вуглецю в молекулі пентану. Але тим самим визначається однозначно і розташування атомів водню в цій молекулі. На малюнку 30 представлена структурна формула молекули одного з ізопентанів, а на малюнку 31 відповідне їй двукорневое дерево.
З тих чи інших причин майже всі роботи по теорії графів таять в собі насіння можливих практичних застосувань або принаймні потенційно корисні.
Графи ефективно використовуються в теорії планування і управління, теорії розкладів, соціології, економіці, біології, медицині, в областях прикладної математики.