1   2   3   4   5   6   7   8   9   ...   16
Ім'я файлу: Metod_Diskret_Math_New_Vysotska_PART2.doc
Розширення: doc
Розмір: 5655кб.
Дата: 26.04.2022
скачати
Пов'язані файли:
Курсач Дячка.docx

Лабораторна робота № 5

ТЕОРІЯ ГРАФІВ

Мета роботи: вивчити основні властивості графів, способи подання графів, шляхів та циклів, обхід графів, розфарбовування графів, набуття практичних навичок програмування алгоритмів, що базуються на графах.

Вступ

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

  1. Основні означення та властивості


Графом G = (V, E) називається об’єкт, який заданий парою множин (V, E), де V – множина вершин, E V×V – множина ребер.

Множину вершин графу G позначають V(G), а множину ребер – E(G). Кількість вершин графу n(G) = |V(G)|, а кількість ребер m(G) = |E(G)|.

Граф називається скінченним, якщо множини його вершин і ребер є скінченними.

Кількість вершин n(G) графу називають його порядком.

Якщо для деякого ребра e = (v,w) E(G), то кажуть (див. рис. 1):

• вершини v та w суміжні;

• вершини v та w інцидентні ребру e;

• ребро e інцидентне вершинам v і w;

Орієнтований граф (V, E), де V – скінченна непорожня множина вершин, а E  – множна впорядкованих пар eлементів множини V. Елементи множини E  в орієнтованому графі називають дугами (чи орієнтованими ребрами). Дугу (v, v) називають петлею. 

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

Основні різновиди графів (див. рис. 2):

  1. граф без петель та кратних ребер називається простим (звичайним);

  2. граф без петель, але з кратними ребрами називається мультиграфом;

  3. найбільш загальний вид граф з петлями та кратними ребрами називається псевдографом;

  4. граф з орієнтованими ребрами (дугами) і петлями та без кратних ребер називається простим орієнтованим графом;

  5. граф з орієнтованими ребрами (дугами) та кратними ребрами і петлями називається орієнтованим мультиграфом;



Рис. 2. Типи графів: а) простий граф; б,в) мультиграф; г) псевдограф; е,ж)орієнтований граф; д,є) орієнтований мультиграф

С тепінь вершини в неорієнтованому графі – це кількість інцидент них їй ребер. Степінь вершини позначають .

Приклад 1. У неорієнтованому графі на рис. 3. Степені вершини є наступними: , , , , . Вершина типу називається висячою, а типу – ізольованою.

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

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

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

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

    1.   1   2   3   4   5   6   7   8   9   ...   16

      скачати

© Усі права захищені
написати до нас