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

Існує три основних способи задання графа:

- геометричний;

- табличний;

- абстрактний

- матричний

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

Для початку введемо визначення евклідового простору – це множина послідовностей із n дійсних чисел , у якій відстань між довільними двома точками та визначена так: .

Простою незамкненою кривою в евклідовому просторі називають неперервну криву, що самонеперетинається і з’єднує дві різні точки в (тобто криву, отриману неперервною деформацією прямолінійного відрізка). Аналогічно простою замкненою кривою називають неперервну криву, яка самонеперетинається і кінцеві точки якої співпадають.

Означення 2.1.10. Геометричний граф у просторі – це множина точок простору і множина простих кривих, які задовольняють такі умови:

1) кожна замкнена крива в Г містить лише одну точку з множини Х;

2) кожна незамкнена крива в Г містить лише дві точки з множини Х, які є її граничними точками;

3) криві в Г не мають спільних точок, за виключенням точок множини Х.

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

- геометричні вершини;

- геометричні ребра.

Дводольний граф задають аналогічно стрілочному способу задання відношень:

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

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

Наприклад, для графа, побудованого геометричним способом вище, таблиця матиме такий вигляд.

Введемо поняття невпорядкованого добутку множини на себе.

Нагадаємо, що впорядкованим (декартовим прямим) добутком множини S на себе називають множину впорядкованих пар . Тут – різні елементи, якщо . Символом & позначимо невпорядковану пару елементів – , а невпорядкований добуток позначимо S & S.

Якщо S ´ S складається з k ² впорядкованих пар, то S & S – з k (k +1)/2 різних невпорядкованих пар.

Означення 2.1.11. Абстрактний граф – це сукупність непорожньої множини Х, ізольованої від неї множини Г (можливо і порожньої) і відображення Ф множини Г на Х & Х. Елементи множини Х називають вершинами графа, а Г – ребрами. Ф називають відображенням інцидентності графа: – ребро u інцидентне кожній з вершин і навпаки. Часом відображення Ф не задають у явному вигляді, а записують і читають: “ребро u з’єднує вершини x ₁ і x ₂”.

Якщо Х і Г – скінченні множини (порожня множина теж скінчена), то граф G (Х, Г) – скінчений. У протилежному випадку кажуть, що граф нескінчений.

Введення абстрактного графа дає змогу зберегти найсуттєвіші комбінаторні характеристики графа, на відміну від геометричного.

Наприклад, граф G, наведений вище можна зобразити абстрактним способом так:

, .

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

Нехай G – граф, який має n вершин і m ребер. Графу G можна зіставити матрицю інциденцій розміром , рядки і стовпці якої відповідають вершинам та ребрам графа відповідно. Розглянемо випадок неорієнтованого графа:

Елемент матриці a_ij набуває значення 1 або 0 залежно від того, інцидентне j -е ребро i -й вершині чи ні. Для петлі всі елементи стовпця дорівнюють нулеві.

Наприклад, вище згаданий

граф G має таку матрицю інциденцій: G=

Матриця інциденцій не вказує на існування петлі, тому при току му способі задання графів слід виключати графи з петлями.

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

Матриця суміжності вершин має розмірність п ´ п, де п – кількість вершин графа. Елементи матриці неорієнтованого графа визначають так:

Елементами матриці орієнтованого графа можуть бути такі числа:

Матриця суміжності ребер має розмірність т ´ т, де т – кількість ребер графа. Елементи матриці неорієнтованого графа визначають так:

Матриця суміжності вершин має розмірність п ´ п, де п – кількість вершин графа. Елементи матриці неорієнтованого графа визначають так:

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

а) неорієнтований граф:

б) орієнтований граф:

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

ЛІТЕРАТУРА

1. Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974. – С. 3-16, 136-143.

2. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: Высшая школа, 1976. – С.7-14.

3. Дискретная математика для програмистов / Ф.А.Новиков. – СПб.: Питер, 2002. – С.189-198.

4. Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцький Г.М., Печорін М.К. Основи дискретної математики. – К.: Наукова думка, 2002. – С.224-229, 236-243.

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

Дата добавления: 2014-10-17