Реферат на тему:
Орієнтовані графи
Крім моделі, яка була розглянута у попередніх розділах, у теорії
досліджуються й інші типи графів. Наприклад,
мультиграф ( граф, в якому припускаються кратні ребра, тобто будь-які
дві вершини можна з’єднати декількома ребрами. Псевдограф ( мультиграф,
який може мати петлі, тобто ребра, що з’єднують вершину саму з собою.
Гіперграф ( граф, в якому ребрами можуть бути не лише двоелементні, але
довільні підмножини множини вершин. Нарешті, важливою для різноманітних
практичних застосувань є модель, яка називається орієнтованим графом або
орграфом. У цьому розділі дамо короткий огляд основних понять і
результатів для орграфів.
Орієнтованим графом, або орграфом, G називається пара множин (V,E ), де
Е (V ?V. Елементи множини V називаються вершинами орграфа G, а елементи
множини Е ( дугами орграфа G =(V,E ). Отже, дуга ( це впорядкована пара
вершин. Відповідно, V називається множиною вершин і Е ( множиною дуг
орграфа G.
Якщо е= (v,w) ( дуга, то вершина v називається початком, а вершина w (
кінцем дуги е. Кажуть, що дуга е веде з вершини v у вершину w або
виходить з v і заходить у w. Дугу е і вершини v та w називають
інцидентними між собою, а вершини v i w суміжними.
Дуга (v,v), в якій початок і кінець збігаються називається петлею.
Надалі розглядатимемо тільки орграфи без петель.
Як і звичайний граф, орграф G =(V,E ) може бути заданий шляхом переліку
елементів скінченних множин V i E, діаграмою або за допомогою матриць.
Діаграма орграфа відрізняється від діаграми звичайного графа тим, що
дуги орграфа зображаються напрямленими лініями (відрізками або кривими),
що йдуть від початку до кінця дуги. Напрямок лінії позначається
стрілкою.
Занумеруємо всі вершини орграфа G =(V,E ) натуральними числами від 1 до
n; дістанемо множину вершин V у вигляді {v1,v2,…,vn}. Матрицею
суміжності А орграфа G називається квадратна матриця порядку n, в якій
елемент і-го рядка і j-го стовпчика
1, якщо (vi,vj)(E ;
aij =
0, у противному разі.
Занумеруємо всі вершини орграфа G =(V,E ) числами від 1 до n, а дуги (
числами від 1 до m. Матрицею інцидентності В орграфа G називається
n?m-матриця, в якій елемент і-го рядка і j-го стовпчика
1, якщо вершина vi є початком дуги ej ;
bij = (1, якщо вершина vi є кінцем дуги ej ;
1, якщо вершина vi і дуга ej неінцидентні.
Орграфи G1=(V1,E1) i G2=(V2,E2) називаються ізоморфними, якщо існує таке
взаємно однозначне відображеня ? множини V1 на множину V2, що дуга
(v,w)?Е1 тоді і тільки тоді, коли дуга (? (v),? (w))?Е2.
Очевидно, що теорема 3.1 справедлива і для орграфів.
Півстепенем виходу вершини v (позначається ?+(v)) орграфа G називається
кількість дуг орграфа G, початком яких є вершина v. Півстепенем заходу
вершини v (позначається ?—(v)) орграфа G називається кількість дуг
орграфа G, кінцем яких є вершина v.
Аналогічно теоремі 3.3 може бути доведено таку теорему.
?—(v)= |E |.
Значна частина властивостей та тверджень стосовно звичайних графів може
бути без змін сформульована і для орграфів. Зокрема, це стосується цілих
розділів, таких, наприклад, як планарність або розфарбування графів, в
яких наявність орієнтації ребер не є суттєвою. Певні особливості в
означеннях, постановках задач та методах їх розв’язування виникають при
дослідженні проблем, пов’язаних з маршрутами, зв’язністю, обходами
графів тощо.
Маршрутом або шляхом в орграфі G =(V,E ) називається послідовність його
вершин і дуг
v1, e1, v2, e2, … , ek, vk +1 (3.5)
така, що ei = (vi,vi +1), i=1,2,…,k. Кажуть, що цей маршрут веде з
вершини v1 у вершину vk +1. Число k дуг у маршруті (3.5) називається
його довжиною.
Маршрут, в якому всі дуги попарно різні, називається ланцюгом. Маршрут,
в якому всі вершини попарно різні, називається простим ланцюгом. Маршрут
(3.5) називається замкненим (або циклічним), якщо v1=vk +1. Замкнений
ланцюг називається циклом, а замкнений простий ланцюг ( простим циклом,
або контуром.
Лема 3.2 виконується і для орграфів.
Орграф називається ациклічним (або безконтурним), якщо він не має
жодного циклу.
Якщо існує маршрут, який веде з вершини v у вершину w, то кажуть, що
вершина w є досяжною з вершини v. У цьому випадку відстанню d (v,w) від
вершини v до вершини w називається довжина найкоротшого маршруту, що
веде з v y w. Відстань між вершиною v i вершиною w, яка є недосяжною з
v, позначається символом (.
Лема 3.9. 1). Відношення досяжності на множині вершин орграфа є
транзитивним.
2). Якщо в орграфі G вершина w є досяжною з вершини v, а вершина u є
досяжною з вершини w, то d (v,w)+d (w, u) ? d (v, u).
Вершина v орграфа G називається джерелом, якщо з v є досяжною будь-яка
інша вершина орграфа G. Вершина w називається стоком, якщо вона є
досяжною з будь-якої іншої вершини орграфа G.
Повним орграфом (або турніром) називається орграф G, в якому будь-які
дві вершини є інцидентними одній і тільки одній дузі орграфа G.
Для повних орграфів справедливі такі твердження.
Теорема 3.24. Для довільного повного орграфа G =(V,E ) з n вершинами
виконуються такі рівності
(n (1( ?+(vi)) = |E |=n(n-1)/2;
(?( (vi))2.
Теорема 3.25. У будь-якому повному орграфі завжди є принаймні одне
джерело і принаймні один стік.
Теорема 3.26. У будь-якому повному орграфі існує простий ланцюг, який
приходить через усі вершини орграфа.
Послідовність (3.4) називається напівмаршрутом, якщо кожна дуга еі цієї
послідовності є такою, що або еi = (vi,vi +1), або ei = (vi +1,vi).
(Можна вважати, що при побудові напівмаршруту ми ігноруємо орієнтацію
дуг орграфа). Аналогічно означаються напівланцюг, напівцикл і
напівконтур.
Орграф називається сильно зв’язним, якщо будь-які дві його вершини є
досяжними одна з одної. Орграф називається однобічно зв’язним, якщо для
будь-яких двох його вершин принаймні одна з них є досяжною з іншої.
Орграф називається слабо зв’язним, якщо для будь-яких двох його вершин
існує напівмаршрут, що веде з однієї вершини в іншу.
Маршрут в орграфі G назвемо кістяковим, якщо він містить всі вершини
орграфа G. Сформулюємо необхідні та достатні умови для кожного з типів
зв’язності.
Теорема 3.27. Орграф є сильно зв’язним тоді і тільки тоді, коли він має
замкнений кістяковий маршрут.
Теорема 3.28. Орграф є однобічно зв’язним тоді і тільки тоді, коли він
має кістяковий маршрут.
Теорема 3.29. Орграф є слабо зв’язним тоді і тільки тоді, коли він має
кістяковий напівмаршрут.
Неважко переформулювати теореми 3.9 і 3.10, їхні наслідки та алгоритми
пошуку вшир і вглиб на випадок різних типів зв’язності орграфів. Ці ж
теореми й алгоритми можна пристосувати для обчислення відстаней між
вершинами заданого орграфа.
Орграф, у якому є джерело і немає жодного напівконтура, називається
кореневим деревом. Вхідне дерево ( це орграф, який має стік і не має
жодного напівконтура.
Орграф називається функціональним, якщо кожна його вершина має
півстепінь виходу, рівний 1. Орграф називається ін’єктивним, якщо
півстепінь заходу кожної його вершини дорівнює 1.
Ейлеровим контуром в орграфі G називається контур, що містить всі дуги
орграфа G. Ейлеровим орграфом називається орграф, у якому є ейлерів
контур. Ейлеровим ланцюгом називається ланцюг, що містить усі дуги
орграфа.
Нижченаведена теорема доводиться так само, як у випадку звичайних
графів.
Теорема 3.30. Слабо зв’язний орграф G =(V,E ) є ейлеровим тоді і тільки
тоді, коли у будь-якої його вершини півстепінь виходу дорівнює
півстепеневі заходу.
Гамільтоновим контуром називається контур, що містить усі вершини
орграфа. Орграф, який має гамільтонів контур, називається гамільтоновим
орграфом. Простий ланцюг, що містить всі вершини орграфа, називається
гамільтоновим.
Із теореми 3.26, зокрема, випливає, що повний орграф є гамільтоновим.
Орграф G =(V,E ) називається транзитивним, якщо з того, що (v,w)?Е і (w,
u)?Е випливає (v, u)?Е.
Існує взаємно однозначна відповідність між множиною всіх безконтурних
транзитивних орграфів G =(V,E ) з множиною вершин V = {v1,v2,…,vn} і
петлями в кожній вершині та множиною всіх відношень часткового порядку
на V. Ця бієкція встановлюється так: орграфу G =(V,E ) відповідає
відношення R на V таке, що (vi,vj)(R тоді і тільки тоді, коли (vi,vj)(E,
vi, vj (V.
Список літератури
1. Харари Т. Теория графов.- М.,1973.
2. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов
В.И., Тышкевич Р.И.- М., 1990.
3. Зыков А.А. Основы теории графов.- М., 1987.
4. Оре О. Теория графов.- М., 1980.
5. Свами М., Тхуласираман К. Графы, сети, алгоритмы.- М., 1984.
6. Уилсон Р. Введение в теорию графов.- М., 1977
7. Кристофидес Н. Теория графов. Алгоритмический подход.- М.,1978
8. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы.-М.,1980
Нашли опечатку? Выделите и нажмите CTRL+Enter
