Поняття графа. Основні визначення. Метричні характеристики графів, їх додатки

Уперше поняття «граф» увів в 1936 р. угорський математик Денні Кеніг. Але перша робота з теорії графів належала перу великого Леонарда Ейлера й була написана ще в 1736 р. За допомогою графів зображуються схеми різних доріг, лінії повітряних сполучень, газопроводів, теплотрас, електромереж, а також мікросхеми, дискретні багатокрокові процеси, системи різних бінарних відношень, хімічні структурні формули й інші діаграми й схеми. Застосовуються графи для рішення задач хімії, економіки, електротехніки й автоматики. Також вони широко використовуються в інформатиці й будівництві. Без графів складно аналізувати класифікації в різних науках.

 

Рис. 2.1. Приклади графів:

а — із суміжними вершинами; б — повний; в — із суміжними ребрами;

г — з петлею

Графом називається пара двох кінцевих множин: множина точок і множина ліній, що з'єднують деякі пари точок. У термінах декартіва добутку множина ліній X, що з'єднує пари точок, — це деяка підмножина множини

Точки називаються вершинами,або вузламиграфа, лінії — ребрамиграфа. Приклади графів наведені на рис. 2.1.

Нехай даний граф де — кінцева непуста множина його вершин, а — його ребра. Якщо ребро графа G з'єднує дві його вершини й (тобто то говорять, що це ребро їм інцидентне. Дві вершини графа називаються суміжними,якщо існує інцидентне їм ребро: на рис. 2.1, а суміжними є вершини А і В, А і С. Якщо граф G має ребро у якого початок і кінець збігаються, то це ребро називається петлею. На рис. 2.1, г) петля — Два ребра називаються суміжними,якщо вони мають загальну вершину. На рис.2.1,в) суміжними є, наприклад, ребра й із загальною вершиною С.

Граф може мати ребра з однаковими парами виду Такі ребра називаються кратними,або паралельними.На рис. 2.1, а) кратними є, наприклад, ребра Вершинам А і В інцидентні ребра Кількість однакових пар виду називається кратністю ребра На рис. 2.1, а) ребро АС має кратність, рівну 3, а ребро АВ — кратність, рівну 2. Число ребер, інцидентних вершині А, називається ступенем цієї вершини й позначається (від англ. degree — ступінь). Якщо вершині інцидентна петля, вона дає внесок у ступінь, рівний двом, тому що обидва кінці приходять у цю вершину.

На рис. 2.1, в) вершина А має ступінь, рівну 1, вершина З — 4, вершина D-D—2. Записується це у вигляді: Граф (рис. 2.1, г) містить чотири вершини й шість ребер

Вершина графа, що має ступінь, рівну нулю, називається ізольованої.Граф, що складається з ізольованих вершин, називається нуль-графом.Для нуль-графа Вершина графа, що має ступінь, рівну 1, називається висячою.На рис. 2.1, г) вершина Е — ізольована: а вершини А, В, Е, G, Н на рис. 2.1, в) — висячі.

Теорема 2.1. У графі сума ступенів всіх його вершин -число парному, рівне подвоєному числу ребер графа:

де — число вершин; — число ребер графа.

Вершина називається (парною\непарною), якщо її ступінь -(парне\непарне) число.

На рис. 2.1, в) виходить, у графа вершина D є парної, a F-F— непарної. У теорії графів доведена наступна теорема.

Теорема 2.2.Число непарних вершин будь-якого графа — парне.

Наслідок. Неможливо накреслити граф з непарним числом непарних вершин.

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

Доповненнямграфа називається граф з тими ж вершинами що й граф який має ті й тільки ті ребра які необхідно додати до графа G, щоб він став повним. Очевидно, що граф із кратними ребрами не має доповнення. Наприклад, доповненням графа до графа на рис. 2.1, б) є граф (рис. 2.2).

Доповненням універсальної множини є порожнє, і навпаки. Оскільки граф і його доповнення відрізняються тільки ребрами (множини Х і ) і доповнення графів зводиться до доповнення множини X, то часткою

Рис. 2.2. Доповнення графа

до графа зображеного на рис. 2.1 б случаємо цієї властивості буде наступне правило: доповненням повного графа буде нуль-граф, і навпаки.

Якщо всі пари в множині X є впорядкованими, тобто кортежами довжини 2, то граф називається орієнтованим, орграфом,або спрямованим.Оскільки відразу може бути не відомо про який граф мова йде, у цій главі ми будемо вживати круглі дужки для позначення ребра замість кутових, як це повинне було бути для кортежів. У них буде міститися відповідна пара вершин. У такому випадку ребра прийнято зображувати стрілками. Початкомребра називається вершина, зазначена в кортежі першої, кінцем— друга вершина цієї пари (графічно вона зазначена стрілкою). Ребра орієнтованого графа мають певні фіксовані початок і кінець і називаються дугами.Очевидно, дуги і якщо вони обидві існують, різні:

Рис.2.3.

Ступенем (входу\виходу)вершини орієнтованого графа називається число ребер, для яких ця вершина є (кінцем\початком).

Ступінь входу вершини V будемо позначати а ступінь виходу — На рис. 2.3: , , , ,

, .

Дуги орграфа називаються кратними,якщо вони мають однакові початкові й кінцеві вершини, тобто однакові напрямки. Наприклад, кратні дуги й на рис. 2.3. Послідовність попарно інцидентних вершин неорієнтованого графа, тобто послідовність ребер неорієнтованого графа, у якій друга вершина попереднього ребра збігається з першою вершиною наступного, називається маршрутом.Число ребер маршруту називається довжиноюмаршруту. Наприклад, на рис. 2.1, в) HCDFD — маршрут довжиною 4. Позначення: Очевидно, що якщо — маршрут довжини те й також буде маршрутом довжини Маршрут прийнятий задавати як послідовність ребер, оскільки це більш зручно при наявності кратних ребер. Якщо початкова вершина маршруту збігається з кінцевої, то такий маршрут називається замкнутимабо циклом.У графі (рис. 2.1, г) — цикли довжиною 4, — цикл довжиною 5, — 8-цикл, — 2-цикл, петля — 1-цикл.

Відстаннюміж двома вершинами називається мінімальна довжина із всіх можливих маршрутів між цими вершинами за умови, що існує хоча б один такий маршрут. Позначається як (від лат. distantio — відстань) .

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

У маршруті те саме ребро може зустрітися кілька разів. Якщо ребро зустрілося тільки один раз, то маршрут називається ланцюгом. Наприклад, у графі (рис. 2.1,г) — 3-ланцюг. Якщо —

k-цикл, то будь-яка циклічна перестановка, наприклад також буде k- циклом, оскільки зведеться лише до вибору початкової вершини. Часткою случаємо цього твердження буде наступне: якщо k- цикл є ланцюгом, то для будь-якої циклічної підстановки послідовність також буде k- циклом і ланцюгом.