МІНІСТЕРСТВО АГЕНСТВО ДО ОСВІТИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ
Державне Освітнє Установа Вищого Професійного Освіти Воронезький Державний Технічний Університет (ГОУВПО ВГТУ )
Кафедра: Вищої математики та фізико-математичного моделювання
Курсова робота
з дисципліни Математика
Метричні характеристики графа
Вороніж 2006
Зміст
1. Поняття граф
. Матричне подання графів
. Операції над графами
. Маршрути, ланцюги, цикли
. Метричні характеристики графа
. Додаток теорії графів у різних галузях науки і техніки
. Практична частина
. Лістинг програми
граф матричний суміжність маршрут
1. Поняття граф
Нехай V - непорожнє безліч, V (2) - безліч всіх його двохелементних підмножин. Пара (V, E), де E - довільна підмножина множини V (2), називається графом (неорієнтованим графом). Елементи множини V називаються вершинами графа, а елементи множини E - ребрами. Отже, граф - це кінцеве безліч V вершин і безліч E ребер, E? V (2).
Термін граф вперше з'явився в книзі видатного угорського математика Д. Кеніга в 1936 р, хоча початкові задачі теорії графів сягають ще до Ейлера (XVIII ст.).
Множини вершин і ребер графа G позначається відповідно VG і EG. Вершини і ребра графа називаються його елементами. Число | VG | вершин графа G називається його порядком і позначається | G |.
Якщо | G |=n, | EG |=m, то граф називають (n, m) -графом.
Кажуть, що дві вершини u і v графа суміжні, якщо множина {u, v} є ребром, і не суміжні в іншому випадку. Якщо e={u, v} - ребро, то вершини u і v називають його кінцями. У цій ситуації говорять також, що ребро e з'єднує вершини u і v.
Два ребра називаються суміжними, якщо вони мають загальний кінець.
Вершина v і ребро e називаються інцидентними, якщо v є одним з кінців ребра e, і не інцидентними в іншому випадку.
Зауважимо, що суміжність є відношення між однорідними елементами графа, тоді як инцидентность є відношенням між різнорідними елементами.
Безліч всіх вершин графа G, суміжних з деякою вершиною v, називається оточенням вершини v і позначається NG (v) або просто N (v).
Графи зручно зображати у вигляді малюнків (геометричних графів). Геометричний граф в просторі n-вимірному евклідовому просторі? n є безліч точок простору? n і безліч E простих кривих, таких: 1) що кожна замкнута крива в E містить тільки одну точку v безлічі V; 2) кожна незамкнута крива в E містить рівно дві точки множини V, які є її граничними точками; 3) криві в E не мають спільних точок крім точок з безлічі V. При цьому точки множини V відповідають вершинам графа, а що з'єднують пари точок лінії - ребрах.
Граф G називається повним, якщо будь-які дві його вершини суміжні. Повний граф порядку n позначається Kn.
Граф називається виродженим (порожнім), якщо будь-які дві його вершини не суміжні (тобто у нього немає ребер).
Нехай G і H графи, а?: VG? VH - біекція. Якщо для будь-яких вершин u і v їх образи? (U) і? (V) суміжні в H тоді і тільки тоді, коли u і v суміжні в G, то ця біекція називається ізоморфізмом графів G і H, асами графи G і H -ізоморфними. Ізоморфні графи будемо позначати G? H (атакож H G).
Якщо граф G ізоморфний геометричному графу G laquo ;, то G називається геометричній реалізацією графа G.
Очевидно, що ставлення ізоморфізму графів є еквівалентністю. Отже, безліч всіх графів розбивається на класи так, що графи з одного класу попарно ізоморфні, а графи з різних класах не ізоморфні. Ізоморфні графи природно ототожнювати, тобто вважати співпадаючими (їх можна зобразити одним малюнком). Вони могли б різнитися конкретною природою елементів, але саме це ігнорується при введенні поняття граф .
У деяких ситуаціях все ж таки доводиться розрізняти ізоморфні графи, і тоді корисно поняття поміченого графа raquo ;. Граф порядку n називається поміченим, якщо його вершин присвоєні деякі мітки, наприклад 1, 2, ..., n. Ототожнивши кожну з вершин графа з її номером (і, отже, безліч вершин - з безліччю чисел {1, 2, ..., n}), визначимо рівність помічених графів G і H одного і того ж порядку: G=H тоді і тільки тоді, коли EG=EH.
При необхідності підкреслити, що розглянуті графи розрізняються ...
