Основні визначення і способи представлення графів

Задачі

Для графа G₁ (рис. 4.1.) виконати наступні дії:

визначити тип і записати відношення, що задається графом;

визначити ступені усіх вершин;

записати за допомогою предикатів умови однорідності графа;

визначити, чи є граф однорідним, якщо ні – зробити таким;

записати матрицю суміжності графа.

Рис. 4.1. Граф G₁

Рис. 4.2. Граф G₂

Для графа G₂ (рис. 4.2.) виконати наступні дії:

визначити тип і записати відношення, що задається графом;

визначити ступені і напівступені усіх вершин;

записати матриці суміжності та інцидентності графа.

Для заданих матриць (табл. 4.1., 4.2.) суміжності графа G₃ виконати наступні дії:

Таблиця 4.1

	x1	x2	x3	x4	x5	x6
X1
X2
X3
X4
X5
X6

Таблиця 4.2

	x1	x2	x3	x4	x5
X1
X2
X3
X4
X5

побудувати графи, що відповідають заданим матрицям суміжності;

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

побудувати матрицю інцидентності.

Для заданого відношення j = (M, P), де М = (1, 2, 3, 4) і Р = М²\E_m, побудувати орграф і записати матрицю інцидентності.

По матриці інцидентності графа побудувати матрицю суміжності і графічне представлення графа.

Для заданого графа G₄ (рис. 4.3.) виконати наступні дії:

знайти маршрут довжини 5 і 8 між вершинами х₁ і х₄;

визначити всі ланцюги і всі прості ланцюги між вершинами х₁ і х₄;

визначити всі прості цикли;

визначити ейлерові і гамільтонові цикли і побудувати відповідні матриці суміжності.

Рис. 4.3. Граф G₄

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

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

F_G = ({x₂, x₃, x₄}, {x₄, x₅}, {x₄}, {Æ}, {x₃, x₄, x₅}).

Дається множина прообразів вершин відповідності Г^-1 графа, визначити тип графа, ступені вершин, побудувати графічне представлення.

P = ({x₅}, {x₁, x₂}, {x₂}, {x₁, x₂}, {x₄}, {x₃, x₄})

Побудувати подграф G' графа G, заданого матрицею інцидентності (табл. 4.3., у вершини х₁ петля v1):

Таблиця 4.3

	v1	V2	v3	V4	v5	v6	v7	V8
x1
x2
x3
x4
x5

на безлічі ребер;

на безлічі вершин X’ = {x₁, x₃, x₄}.

Показати, що для довільного простого графа G = (Х, Г), що містить n вершин, справедлива рівність 2|Г| = S_і=1ⁿs(хі). Перевірити, чи виконується дана рівність для мульти і псевдо графів.

Визначити умови існування і привести приклад графа, що містить:

ейлерів цикл;

гамільтонов цикл;

гамільтонов цикл, але не ейлерів цикл;

ейлерів цикл, але не гамільтонов цикл.

Теоретико-множинні операції над графами

Задачі

Графи G і H задані множинами фактор-безлічей F_G = ({x₂}, {x₂, x₃}, {Æ}) і F_H = ({x₂}, {x₁}), необхідно визначити:

GÈH, GÇH;

`G, `H;

G\H, H\G;

GÅH, GÅ`H.

Графи G, H і P задані множинами фактор-безлічей F_G = ({x₂, x₃}, {x₃}, {Æ}), F_H = ({x₁}, {x₁, x₂}) і P = ({x₁}, {x₂}, {x₃}), необхідно визначити:

G\H, H\G;

G\PÇH;

(PÈH)\(GÇH);

(PÅH)Ç(G\H).

Для графів G і H, заданих множинами фактор-безлічей F_G = ({x₁, x₂}, {x₂}) і F_H = ({y₁}, {y₁, y₂}), побудувати граф, рівний:

декартовому добутку;

композиції.

Для графів G, H і P, заданих матрицями суміжності (відповідно табл. 4.4., 4.5. і 4.6.), побудувати матрицю суміжності графа, рівного:

GÈH, GÇH;

`G, `H;

G\H, H\G, G\P, P\H;

(G\P)Ç(GÈ`H);

(GÅ`H)Ç(`PÈG).

Таблиця 4.4

	x1	x2	x3
x1
x2
x3

Таблиця 4.5

	x1	x2	x3	X4
x1
x2
x3
x4

Таблиця 4.6

	X1	x2	x3	x4
x1
x2
x3
x4

Для графів G і H, заданих матрицями інцидентності (відповідно табл. 4.7. і 4.8., дуги, що з'єднують однойменні вершини в різних графах, мають однакове позначення), побудувати матрицю інцидентності результуючого графа, рівного:

GÈH, GÇH;

`G, `H;

G\H, H\G;

(GÅH), (`GÅ`H).

Таблиця 4.7

	v1	v2	v3	v4	v5	V6
X1		-1			-1
X2	-1
X3			-1	-1		-1

Таблиця 4.8

	v1	v2	V3
x1
x2	-1	-1
x3			-1

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

декартовому добутку;

композиції.

Таблиця 4.9

	x1	x2	X3
x1
x2
x3

Таблиця 4.10

	x1	x2	X3
x1
x2
x3

Для графів G і H задачі 6, заданих матрицями суміжності і (відповідно табл. 4.9. і 4.10.), розробити блок-схеми і написати програми виконання операцій:

GÈH, GÇH;

`G, `H;

G\H, H\G;

(GÅH);

(GÅ`H)Ç(`GÈH).

Для графів G і H, заданих множинами фактор-безлічей F_G = ({x₁, x₂}, {x₂}) і F_H = ({y₁}, {y₁, y₂}), розробити блок-схеми і написати програми виконання операцій:

декартового добутку;

композиції.