КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Основні положення
Розділ 2. ОСНОВИ ТЕОРІЇ ГРАФІВ
Теорію графів почали розробляти для розв'язання деяких задач про геометричні конфігурації, що складаються з точок і ліній. Визначення графа можна дати як сукупності двох множин V(точок) і E (ліній, дуг), між елементами яких визначене відношення інцидентності, причому кожний елемент е Î E інцидентний двом елементам v', v" Î V. Елементи множини V називаються вершинами графа G, елементи множини Е - його ребрами. Вершини і ребра графа G називають ще його елементами і замість е Î Е і v ÎV пишуть e Î G і v Î G. У деяких графах інцидентні ребру вершини нерівноправні, вони повинні, наприклад, розглядатися у визначеному порядку. Тоді кожному з ребер можна приписати напрямок від першої із інцидентних вершин до другої. Спрямоване ребро часто називають дугою, а граф, що їх містить, - орієнтованим. У противному випадку (інцидентні ребру вершини рівноправні) граф будемо називати неорієнтованим.
Початок Кінець 1 2 Дуга: виходить входить
Рис.2.1. Зображення орієнтованого графа: 1-дуга виходить; 2-дуга входить.
Наочне уявлення про граф можна одержати, якщо уявити собі деяку множину точок площини Х, що називаються вершинами, і множину спрямованих відрізків U, що з'єднують усі або деякі з вершин і називаються дугами. Математично граф G можна визначити як пару множин Х і U: G = (X, U). Граф називається повним, якщо дві різні його вершини з'єднані лише одним ребром. На рис. 2.2 зображений граф, вершинами якого є точки a, b, c, d, e, g, h, а дугами - відрізки (a, a), (c, b), (c, d), (c, e), (d, c), (d, d), (e, d), (g, h).
Так, для графа, зображеного на рис.2.2, відображення визначається в такий спосіб: Гa=a; Гb=Æ; Гc={b, d, e}; Гd={c, d}; Гe=d; Гg=h; Гh=Æ. Неважко помітити, що дане визначення графа цілком збігається з визначенням відношення на множині. Введемо деякі поняття і визначення, необхідні для опису різноманітних видів графів. Підграфом GA графа G=(X, Г) називається граф, в який входить лише частина вершин графа G, що утворює множину А, разом із дугами, що з'єднують ці вершини, наприклад обкреслена пунктиром область А на рис.2.2. Математично підграф позначається в такий спосіб: GA=(A,ГA), де АÍХ, ГАХ=(ГХ)ÇА. Частковим графом GD стосовно графа G=(X, Г) називається граф, що містить тільки частину дуг графа G, тобто визначений умовою: GD=(X, D), де Dx Í ГX. Наприклад, нехай G=(X, Г) - карта шосейних доріг України. Тоді карта шосейних доріг Дніпропетровської області являє собою підграф, а карта головних доріг України - це частковий граф. Іншими важливими поняттями для графа є поняття шляху і контуру. Дуга, що з'єднує вершини a і b, спрямована від а до b і позначається u=(a, b). Визначення Шляхом у графі G називають таку послідовність дуг m=(u1,...,uk), в якій кінець кожної попередньої дуги збігається з початком наступної. Шлях m, послідовними вершинами якого є вершини a, b,..., m, позначається через m=(a, b,..., m). Довжиною шляху m=(u1,...,uk) називають число l(m)=k, що дорівнює числу дуг, які складають шлях. Іноді кожній дузі ui приписують деяке число l(ui), яке називається довжиною дуги. Тоді довжина шляху визначається як сума довжин дуг, що складають шлях k l (m)=S l(ui). I=1 Шлях, в якому ніяка дуга не зустрічається двічі, називається простим. Шлях, в якому ніяка вершина не зустрічається двічі, називається елементарним. Контур - це кінцевий шлях m=(x1,..., xk), де початкова вершина х1 обов'язково збігається з кінцевою хk. При цьому контур називається елементарним, якщо всі його вершини різноманітні (за винятком початкової і кінцевої, що збігаються). Контур одиничної довжини, утворений дугою вигляду (а, а), називається петлею. Так, на рис.2.2 (e, d, c, b) - шлях, а (c, e, d, c) - контур, (d, d) - петля. 1 (e, d, c, b) - шлях, а (c, e, d, c) - контур, (d, d) - петля. Іноді графи зручно подавати у вигляді матриць, зокрема у вигляді матриць суміжності та інцидентності. Попередньо дамо два визначення. Вершини x і y є суміжними, якщо вони різноманітні і якщо існує дуга, що йде з x до y. Дугу u називають інцидентною вершині х, якщо вона заходить у цю вершину або виходить з неї. Позначимо через х1,..., хn вершини графа, а через u1,...,um - його дуги. Введемо числа: ì 1, якщо є дуга, що з'єднує вершину i із вершиною j; rij = í î 0, якщо такої дуги немає.
Квадратна матриця R=[rij] порядку (n x n) називається матрицею суміжності графа. Введемо числа: ì +1, якщо uj виходить із xi ; Sij = í -1, якщо uj заходить у xi ; î 0, якщо uj не інцидентна xi.
Тоді матриця S=[Sij] порядку (n x m) називається матрицею інцидентності для дуг графа. Матриці інцидентності в описаному вигляді застосовні тільки до графів без петель. У випадку наявності в графі петель цю матрицю варто розчленувати на дві півматриці: позитивну і негативну. На рис.2.3 наведений граф без петель, для якого матриці суміжності та інцидентності мають такий вигляд:
Матриця суміжності I, J 1 2 3 4 5 1 0 1 0 1 1 2 0 0 0 0 0
4 0 1 1 0 1 5 0 0 0 1 0
Звичайно графи, які розглядаються, є кінцевими, тобто кінцеві множини їхніх елементів (вершин і ребер). Тому скінченність цих графів не буде додатково визначатися. Приклади орієнтованих графів показані на рис.2.4.
Матриця інцидентності
а b с
d e f g к (кратне ребро)
Рис.2.4. Приклади орієнтованих графів
В наведених прикладах варіант "b" подає граф із порожньою множиною ребер. Граф "е" ілюструє недосяжність двох вершин, а "g" - граф із петлею.
Дата добавления: 2014-11-29; Просмотров: 642; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |