Реферат: Моделі і методи прийняття рішень

Поняття граф ввів у 1736 році Ейлер. Граф Gмістить дві множиниG=(V,E), де V - множина вершин (вузлів 1...n), E - множина ребер. Коли пари вершин впорядковані - то граф орієнтований, інакше - неорієнтований. Впорядкована пара позначається <i,j>, невпорядкована – (i,j). У зважених графах кожне ребро має вагу.

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

Шляхом називається послідовність вершин між двома вершинамиp і q.

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

а) б)

Рис.2. Зображення орієнтованого (а) і неорієнтованого (б) графів.

3.2 Способи задання графів

Існує послідовний і зв’язний спосіб задання графів.

Послідовна форма використовує квадратну таблицю (Graf(n,n), n- вершин), яку називають матрицею суміжності. Якщо є зв’язок між вершинами, то Graf(I,j)=1, інакше Graf(I,j)=0.

а)б)

Рис.3. Матриці суміжності графів з рис.2.: а – неорієнтованого, б – орієнтованого

Матриця інцидентності відображає зв’язок n вершин за допомогою m дуг, розмір матриці інцидентності (n*m), але вона менш зручна, ніж матриця суміжності.

Інша форма задання графу – список зв’язності. Граф зnвершинами буде задаватися списками – по одному для кожної вершини. Список для вершини і містить вершини, суміжні з і.

3.3 Дерева

Дерево – це орієнтований ациклічний граф, для якого виконуються такі умови:

1) існує одна вершина, в яка не входить жодне ребро (корінь);

2) у будь-яку вершину, крім кореня, входить лише одне ребро;

3) з кореня можна знайти унікальний шлях до кожної вершини дерева.

Орієнтований граф з кількох вершин – ліс. Бінарне дерево – кожна вершина має два нащадки. При пошуку певного вузла у дереві використовують пряме і зворотне проходження вузлів.

Способи зберігання дерев

Послідовне зберігання ділиться на рівневі і діжкове.

Рівневе: для кожного рівня дерева послідовно вказаються його вузли.

Дужкове: дужками вказуються нащадки даного вузла.

Зв’язне зберігання – списки, кожен список містить вказівними на нащадків.

Пошук у глибину і ширину

Пошук в глибину – послідовно відвідуються всі нові вершини –нащадки (якщо вершина була відвідана, то вона перестає бути новою).

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

Остові дерева

Довільне дерево <V, T> неорієнтованого графу G=<V, E> називається остовим.

Ейлерові шляхи

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