На головну

теорія графів

  1.  I. ТЕОРІЯ (32 години)
  2.  III. Загальна теорія неврозів
  3.  Quot; Соціологізму "як соціальна теорія
  4.  V. ПСИХОАНАЛІТИЧНА ТЕОРІЯ ОСОБИСТОСТІ
  5.  XIII. Теорія відтворення Дестюта де Траси
  6.  А. Маслоу (Maslow A.H.): теорія самоактуалізації
  7.  Адміністративна теорія А. Файоля

поняття графа

Початок теорії графів часто ведуть від 1736 і пов'язують з рішенням Ейлером знаменитої задачі про Кенигсбергских мостах.

З C

A D A D

В B

Жителям в ті далекі часи, щоб надати недільного гулянню осмисленість, пропонувалося вийшовши з дому (на будь-якій ділянці суші (А, В, С або D) Пройти по всіх мостах строго по одному разу і повернутися додому ....

На другому малюнку цей кострубатий план намальований у вигляді графа.

 Слід зазначити деякі практичні особливості теорії графів. слово граф однокореневе зі словом графіка. Тому не дивно, що багато завдань теорії графів представляються у вигляді спеціального малюнка - графа. Однак, це, як правило, можливо тільки для найпростіших варіантів завдань. Малювати графи для задач з сотнями вершин і тисячами дуг, якщо і можливо, то безглуздо. Втрачається головна перевага малюнка - наочність. Крім того, сьогодні під час вирішення завдань теорії графів широко використовується обчислювальна техніка, а для неї - рішення задачі, заданої малюнком - одне з найбільш незручних уявлень, які можна придумати. А наочність комп'ютер розуміє по-своєму : - |

Граф G задається як сукупність двох сутностей: безлічі вершин Х і безлічі з'єднань - безлічі дуг або ребер.Г. G = <Г, Х>,

Графічно це може виглядати наступним чином:


m
b

e

x5

j


x4


Традиційна «аналітична» запис для цього малюнка буде:

Гx1 = {X2} Гx4 = {X3, x3}

Гx2 = {X2, x3, x4} Гx5 = {X2}

Гx3 = ?

Інший спосіб завдання графа - за допомогою матриці інціденцій.

  a b d h j e m
х1  -1            
х2  +1  -1      -1  +1
х3      +1  -1      
х4        +1  -1  +1  
х5          +1    -1

Найпопулярніший вид матриці для графів - Матриця смежностей

   х1  х2  х3  х4  х5
 х1        
 х2    
 х3        
 х4        
 х5        

Граф з ненаправленої сполуками (ребрами) - неорієнтовний.

Граф з спрямованими стрілками (Дугами) - орієнтований (орграф).

мультіграф - Граф, між вершинами якого може бути більше однієї дуги.

У графах важливо їх топологічний властивість: тобто з'єднання певних вершин. А саме по собі взаєморозташування ролі не грає, як і відстані між об'єктами.

a b c a

 a 1

 3 1

 c b c 3

 1 2 3 2 b

2


Один і той же граф.

Дуга може виходити з вершини або заходити в неї. Вона буде відповідно називатися вихідної або заходить.

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

довжина шляху вимірюється числом пройдених дуг.

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

Контур довжиною в одиницю - петля.

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

шлях називається елементарним, Якщо будь-яка вершина на цьому шляху один раз.

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

Вершини інцідентние однієї дузі називаються суміжними.

Полустепені результату вершини x - r-(X) називається число вихідних з неї дуг

r-(x3) = 3.

Полустепені заходу вершини x - r+(X) називається число заходять в неї дуг

r+(x3) = 2.

r = r-(X) + r+(X). - Ступінь вершини х.

теорема: У будь-якому графі число вершин з непарної ступенем парне.

Докази походять з того, що сумарна ступінь всіх вершин - число парне (у кожної дуги 2 кінця!). Якщо прибрати ступеня всіх парних вершин, то залишиться парне число сумарної ступеня непарних вершин. А це можливо тільки якщо число вершин з непарної ступенем парне.

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

Доказ замінимо рішенням завдання «про шахістів»:

Нехай серед n людина немає двох таких, хто зіграв би однакове число партій в шаховому турнірі. Тоді обов'язково повинно бути:

1-ий зіграв: 0 партій

2-ий зіграв: 1 партію

:

n-ий зіграв n-1 партій

тобто з вершини n-го гравця виходить (n-1) стрілка, а в 0-ую не входить жодна. Але цього не може бути.

Граф GA = <ГA, A> - називається подграфом графа G = <Г, X>, якщо A I Х, ГA I Г.

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

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




 Несуперечливість і повнота аксіоматичної теорії числення висловів |  Аксіоматичні теорії першого порядку |  система Генцен |  система Аристотеля |  Категоричні висловлювання. |  Модальні логіки. |  теорія Автоматів |  приклади автоматів |  виходів |  мінімізація автоматів |

© um.co.ua - учбові матеріали та реферати