Визначення графа - студопедія

Розглянемо безліч V. що складається з з'єднаних певним чином точок. Елементи - вершини графа. ГрафG = G (V) з безліччю вершин V є деяке сімейство поєднань або пар виду

вказують, які вершини вважаються з'єднаними.

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

Можна визначити поняття графа інакше, якщо уявити собі деяке безліч точок площині V. званих вершинами. і безліч спрямованих відрізків E, що з'єднують всі або деякі з вершин і званих дугами. Тобто математично граф G можна визначити як пару множин G = (V, E). Прикладами графа може бути карта автомобільних або залізниць, схеми з'єднання електричних ланцюгів і т.п.

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

Так, рис. 2.1 зображений граф, вершинами якого є точки a, b, c, d, e, g, h, а дугами - відрізки (a, a), (c, b), (c, d), (c, e), (d, c), (d, d), (e, d), (g, h). Відображення наведеного графа буде визначатися таким чином: Г а =; Г b =Æ; Г з =; Г d =; Г е =; Г g =; Г h =Æ.

Неважко бачити, що дане визначення графа повністю збігається з визначенням відносини на множині.

Зі сказаного можна визначити, що графом G (V, E) називається сукупність двох множин - непорожньої безлічі V (безлічі вершин) і безлічі Е його двоелементний підмножин множини V (Е - безліч ребер).

У визначенні ребра можна приймати чи не приймати до уваги порядок розташування двох його кінців. Якщо цей порядок несуттєвий, тобто якщо. то E є неорієнтоване ребро, якщо ж порядок суттєво, то D називають орієнтованим ребром, і при цьому vi початкова вершина, - кінцева вершина.

Граф називається орієнтованим. якщо орієнтовані всі його ребра.

неорієнтовані граф орієнтований граф

У ряді випадків має місце змішані графи.

Як у випадку орієнтованого, так і неорієнтованого ребра кажуть, що ребро E = (vi. Vj) інцидентне вершин vi і vj, а також, що вершини vi і vjінцідентни ребру E. Дві вершини, інцидентні одному ребру називаються суміжними. Вершина, що не инцидентная ніякому ребру, називається ізольованою. Часто має сенс враховувати тільки неізольовані вершини.

Число інцідентних вершині u ребер називається ступенем вершини і позначається deg (u).

Граф, що складається тільки з ізольованих вершин, називається нуль-графом.

Найбільш важливим випадком є ​​повний графG = (V, E), ребрами якого є всілякі пари () для двох різних вершин vi і vj з V. Повний граф з вершинами позначається. На рис. 2.3 наведені повні графи і відповідно.

В орієнтованому повному графі є пари ребер, по одному в кожному напрямку, що з'єднують будь-які дві різні вершини vi і vj. Ребра, у яких обидві кінцеві точки співпадають L = (a, a) називаються петлею.

(Див. Мал. 2.1 вершини "а", "d"). Петля зазвичай вважається неориентированной. Можна розширити повний граф до повного графа з петлями, додаючи петлю в кожній вершині.

Допускається, щоб пара вершин з'єднувалася декількома різними ребрами.

Для кожного орієнтованого графа існує зворотний графG *. одержуваний зміною орієнтації кожного з ребер графа G на протилежне.

Для кожного орієнтованого графа існує також співвіднесений неорієнтовний графGu. ребрами якого є ребра графа G. але вже без орієнтації. Іноді зручно перетворити неорієнтовані граф G в орієнтований граф Gd за допомогою процесу подвоєння, що складається в заміні кожного ребра G парою ребер з тими ж вершинами і приписуванням їм (ребрах) протилежних орієнтацій.

Граф називається плоским якщо він може бути зображений на площині так, що всі перетину ребер є вершинами G.

Регулярні графи. Граф називається регулярним, або однорідним, якщо всі його вершини мають одну й ту ж саму ступінь. Якщо ступінь кожної вершини дорівнює k. то граф називають регулярним графом ступеня k. Наприклад, повний граф n-го порядку є регулярний граф ступеня k = n-1. Наприклад, регулярні графи ступеня 3 називають кубічними, або 3-х валентними графами. Як приклад на рис. 2.4 наведено кубічний граф Петерсена.

Платонова графи. Платоновим графами називаються графи, утворені вершинами і ребрами п'яти правильних багатогранників - Платонових тел: тетраедра, куба, октаедра, Додекаедр, ікосаедра.

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

ПодграфомGA графа G = (V, Г) називається граф, в який входить лише частина вершин графа G, що утворюють безліч А, разом з дугами, що з'єднують ці вершини. Наприклад, окреслена пунктиром область на рис. 2.1. Математично це записується в такий спосіб:

Частковим графом GD по відношенню до графу G = (V, Г) називається граф, що містить тільки частину дуг графа G. тобто визначається умовою

Наприклад, якщо G = (V, Г) - карта автомобільних дорогУкаіни, тоді карта доріг Нижегородської області є підграф, а карта головних автомагістралейУкаіни - частковий граф.

Шляхом в графі G називають таку послідовність дуг d = (u1. U2. ... uk), в якій кінець кожного попереднього дуги збігається з початком наступної. Шлях d. послідовними вершинами якого є вершини a, b, c, ... m позначається через d = (a, b, c, ... m).

Довжиною путіd = (u1. U2. ... uk) називають число l (d) = k, яка дорівнює кількості дуг, що складають шлях d. Іноді кожної дузі ui приписують деяке число l (ui), зване довжиною дуги. Тоді довжина шляху визначається як сума довжин дуг, що складають шлях

Шлях, в якому ніяка дуга не зустрічається двічі, називається простим. Шлях, в якому ніяка вершина не зустрічається двічі, називається елементарним.

Контур - це кінцевий шлях d = (v1. V2. ... vk), у якого початкова вершина х1 збігається з кінцевою vk. При цьому контур називається елементарним, якщо всі його вершини різні (за винятком початкової і кінцевої, які збігаються). Контур одиничної довжини, утворений дугою виду (а, а), називається петлею. Так, на рис. 2.1 (e, d, c, b) - шлях, (с, e, d, c) - контур, (d, d) -петлі.

Для неорієнтованого графа відповідно вводяться поняття ланцюга і циклу. Ланцюг (цикл) називається ейлеровой. якщо вона проходить через всі ребра по одному разу. Ланцюг (цикл) називається гамильтоновой. якщо вона проходить через всі вершини графа по одному разу.