Поняття графа. 
Способи завдання графів (реферат)

Реферат на тему:

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

Нехай V еяка непорожня скінченна множина, а V (2) ножина всіх двохелементних підмножин (невпорядкованих пар різних елементів) множини V.

Графом (неорієнтованим графом) G називається пара множин (V, E), де E овільна підмножина множини V (2) (E 2)) — позначається G =(V, E).

Елементи множини V називаються вершинами графа G, а елементи множини E ебрами графа G. Відповідно V називається множиною вершин і E ножиною ребер графа G.

Традиційно ребра {v, w} записуються за допомогою круглих дужок (v, w) (іноді просто vw).

Граф, який складається з однієї вершини, називається тривіальним.

Оскільки для тривіального графа або так званих порожніх графів G =(V, переважну більшість властивостей та тверджень перевірити неважко, то надалі не будемо кожен раз при формулюванні та доведенні тих чи інших загальних тверджень теорії графів спеціально обумовлювати, що йдеться про нетривіальні графи (при цьому для тривіального або порожнього графів результат може бути дещо іншим).

Нехай задано граф G =(V, E). Якщо (v, w) то кажуть, що вершини v i w є суміжними, у противному разі вершини v i w є несуміжними. Якщо е=(v, w) ебро графа, то вершини v i w називаються кінцями ребра е. У цьому випадку кажуть також, що ребро е з'єднує вершини v i w. Вершина v і ребро е називаються інцидентними, якщо v є кінцем е.

Два ребра називаються суміжними, якщо вони мають спільну вершину.

Існує декілька способів завдання графів.

Одним зі способів завдання графа G =(V, E) є завдання кожної з множин V і E за допомогою переліку їх елементів.

Приклад 3.1. Граф G1=(V1,E1), V1={v1,v2,v3,v4} і E1={(v1,v3), (v1,v4),(v2,v3),(v2,v4),(v3,v4)} е граф із чотирма вершинами і п’ятьма ребрами.

А граф G2=(V2,E2), V2={v1,v2,v3,v4,v5} і E2={(v1,v2),(v2,v4),(v1,v5), (v3,v2),(v3,v5),(v4,v1),(v5,v4)} раф із п’ятьма вершинами і сімома ребрами.

Граф G =(V, E) зручно зображати за допомогою рисунка на площині, який називають діаграмою графа G. Вершинам графа G ставляться у бієктивну відповідність точки площиниточки, що відповідають вершинам v i w, з'єднуються лінією (відрізком або кривою) тоді і тільки тоді, коли v i w суміжні вершини. Зрозуміло, що діаграма графа змінюватиме свій вигляд у залежності від вибору відповідних точок на площині.

Приклад 3.2. На рисунку 3.1 зображені діаграми графів G1 i G2 з попереднього прикладу.

G1 G2.

Рис 3.1.

Графи можна задавати також за допомогою матриць.

Занумеруємо всі вершини графа G натуральними числами від 1 до n. Матрицею суміжності A графа G називається квадратна.

nматриця, в якій елемент aij i-го рядка і j-го стовпчика дорівнює 1, якщо вершини vi та vj з номерами i та j суміжні, і дорівнює 0 у противному разі.

Приклад 3.3. Для графів G1 i G2 маємо відповідно.

A1= $$\begin{array}{c}\text{0011}\\ \text{0011}\\ \text{1101}\\ \text{1110}\\ \\ \mathit{righ}\\ \\ \\ \\ \begin{array}{c}\left(\right)\left(\right)\left(\right)\end{array}\\ \hfill \\ \end{array}$$ i A2= $$\begin{array}{c}\text{1\hspace{0.17em}011}\\ \text{10\hspace{0.17em}110}\\ \text{1\hspace{0.17em}001}\\ \text{11\hspace{0.17em}001}\\ \text{10\hspace{0.17em}110}\\ \\ \mathit{righ}\\ \\ \\ \\ \begin{array}{c}\left(\right)\left(\right)\left(\right)\left(\right)\end{array}\\ \hfill \\ \end{array}$$.

Очевидно, що матриці суміжності графів иметричні.

Занумеруємо всі вершини графа G числами від 1 до n і всі його ребра ислами від 1 до m. Матрицею інцидентності B графа G називається nматриця, в якій елемент bij i-го рядка і j-го стовпчика дорівнює 1, якщо вершина vi з номером i інцидентна ребру ej з номером j, і дорівнює 0 у противному разі.

Приклад 3.4. Для графів G1 і G2 маємо (ребра графів нумеруємо в тому порядку, в якому вони виписані в прикладі 3.1).

B1= $$\begin{array}{c}\text{11\hspace{0.17em}000}\\ \text{110}\\ \text{10\hspace{0.17em}101}\\ \text{1\hspace{0.17em}011}\\ \\ \mathit{righ}\\ \\ \\ \\ \begin{array}{c}\left(\right)\left(\right)\left(\right)\end{array}\\ \hfill \\ \end{array}$$ і B2= $$\begin{array}{c}\text{1\hspace{0.17em}010\hspace{0.17em}010}\\ \text{1\hspace{0.17em}101\hspace{0.17em}000}\\ \text{1\hspace{0.17em}100}\\ \text{100\hspace{0.17em}011}\\ \text{10\hspace{0.17em}101}\\ \\ \mathit{righ}\\ \\ \\ \\ \begin{array}{c}\left(\right)\left(\right)\left(\right)\left(\right)\end{array}\\ \hfill \\ \end{array}$$.

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

Приклад 3.5. Для графів G1 і G2 маємо списки.

G1: G2:

v1: v3, v4 v1: v2, v4,v5.

v2: v3, v4 v2: v1, v3,v4.

v3: v1, v2,v4 v3: v2, v5.

v4: v1, v2,v3 v4: v1, v2,v5.

v5: v1, v3,v4.

Вибір та зручність того чи іншого зі способів завдання графів залежать від особливостей задачі, яка розв’язується.

Список літератури.

1. Харари Т. Теория графов.- М., 1973.

2. Лекции по теории графов / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р.И.- М., 1990.

3. Зыков А. А. Основы теории графов.- М., 1987.

4. Оре О. Теория графов.- М., 1980.

5. Свами М., Тхуласираман К. Графы, сети, алгоритмы.- М., 1984.

6. Уилсон Р.

Введение

в теорию графов.- М., 1977.

7. Кристофидес Н. Теория графов. Алгоритмический подход.- М., 1978.

8. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы.-М., 1980.