Основні визначення і способи представлення графів
Задачі
Для графа G1 (рис. 4.1.) виконати наступні дії:
визначити тип і записати відношення, що задається графом;
визначити ступені усіх вершин;
записати за допомогою предикатів умови однорідності графа;
визначити, чи є граф однорідним, якщо ні – зробити таким;
 |
записати матрицю суміжності графа.
 |
Рис. 4.1. Граф G1
Рис. 4.2. Граф G2
Для графа G2 (рис. 4.2.) виконати наступні дії:
визначити тип і записати відношення, що задається графом;
визначити ступені і напівступені усіх вершин;
записати матриці суміжності та інцидентності графа.
Для заданих матриць (табл. 4.1., 4.2.) суміжності графа G3 виконати наступні дії:
Таблиця 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) і Р = М2\Em, побудувати орграф і записати матрицю інцидентності.
По матриці інцидентності графа побудувати матрицю суміжності і графічне представлення графа.
Для заданого графа G4 (рис. 4.3.) виконати наступні дії:
знайти маршрут довжини 5 і 8 між вершинами х1 і х4;
визначити всі ланцюги і всі прості ланцюги між вершинами х1 і х4;
визначити всі прості цикли;
визначити ейлерові і гамільтонові цикли і побудувати відповідні матриці суміжності.
 |
Рис. 4.3. Граф G4
За допомогою формул логіки предикатів записати умову, при якій граф є двочастковим, показати, що будь-яке дерево можна представити у виді двочасткового графа.
Дається множина фактор-безлічей, визначити тип графа і ступені його вершин, а також побудувати графічне представлення.
FG = ({x2, x3, x4}, {x4, x5}, {x4}, {Æ}, {x3, x4, x5}).
Дається множина прообразів вершин відповідності Г-1 графа, визначити тип графа, ступені вершин, побудувати графічне представлення.
P = ({x5}, {x1, x2}, {x2}, {x1, x2}, {x4}, {x3, x4})
Побудувати подграф G' графа G, заданого матрицею інцидентності (табл. 4.3., у вершини х1 петля v1):
Таблиця 4.3
| v1 | V2 | v3 | V4 | v5 | v6 | v7 | V8 | |
| x1 | ||||||||
| x2 | ||||||||
| x3 | ||||||||
| x4 | ||||||||
| x5 |
на безлічі ребер;
на безлічі вершин X’ = {x1, x3, x4}.
Показати, що для довільного простого графа G = (Х, Г), що містить n вершин, справедлива рівність 2|Г| = Sі=1ns(хі). Перевірити, чи виконується дана рівність для мульти і псевдо графів.
Визначити умови існування і привести приклад графа, що містить:
ейлерів цикл;
гамільтонов цикл;
гамільтонов цикл, але не ейлерів цикл;
ейлерів цикл, але не гамільтонов цикл.
Теоретико-множинні операції над графами
Задачі
Графи G і H задані множинами фактор-безлічей FG = ({x2}, {x2, x3}, {Æ}) і FH = ({x2}, {x1}), необхідно визначити:
GÈH, GÇH;
`G, `H;
G\H, H\G;
GÅH, GÅ`H.
Графи G, H і P задані множинами фактор-безлічей FG = ({x2, x3}, {x3}, {Æ}), FH = ({x1}, {x1, x2}) і P = ({x1}, {x2}, {x3}), необхідно визначити:
G\H, H\G;
G\PÇH;
(PÈH)\(GÇH);
(PÅH)Ç(G\H).
Для графів G і H, заданих множинами фактор-безлічей FG = ({x1, x2}, {x2}) і FH = ({y1}, {y1, y2}), побудувати граф, рівний:
декартовому добутку;
композиції.
Для графів 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, заданих множинами фактор-безлічей FG = ({x1, x2}, {x2}) і FH = ({y1}, {y1, y2}), розробити блок-схеми і написати програми виконання операцій:
декартового добутку;
композиції.