14.3 Приклади розв’язання типових завдань
1. Запишіть матриці суміжності S та інциденцій R для псевдографа, який зображено на рис. 14.1.
е3
Рисунок 14.1
Елемент sik матриці суміжності S мультиграфа G(V,E) дорівнює кількості ребер, які з’єднують вершини vi та vk. Елемент rij матриці інциденцій R вершин та ребер графа G дорівнює 1, якщо вершина vi інцидентна ребру ei та дорівнює 0 у протилежному випадку.
2. Запишіть матриці суміжності M та інциденцій N для орграфа на рис. 14.2.
Елемент
mik
матриці суміжності M
орграфа G(V,E) дорівнює
кількості дуг, які йдуть з вершини vi
у вершину vk.
Матриця інциденцій графа G
– це матриця
,
Рисунок 14.2
3. Задано
граф G(V,E)
(рис. 14.3) та його частини: H1(V1,E1)
(рис. 14.4) та H2(V2,E2)
(рис. 14.5). Знайти:
Рисунок 14.3
Рисунок 14.4 |
Рисунок 14.5 |
Граф H є частиною графа G, оскільки V(H)V(G), E(H)E(G). Об’єднанням графів H1(V1,E1) і H2(V2,E2) є граф G'(V',E')=H1(V1,E1)H2(V2,E2). Перетином графів H1(V1,E1) та H2(V2,E2) буде граф
G''(V'',E'')=H1(V1,E1)H2(V2,E2).
Враховуючи
вхідні дані у задачі, граф
зображено
на рис. 14.6,
–
на рис. 14.7,
–
на рис. 14.8,
– на рис. 14.9.
Рисунок 14.6 |
Рисунок 14.7
|
Рисунок 14.8 |
Рисунок 14.9 |
14.4 Контрольні запитання та завдання
1. Дати визначення терміну граф.
2. Дати визначення терміну нуль-граф.
3. Дати визначення терміну повний граф.
4. Дати визначення терміну мультиграф.
5. Дати визначення терміну псевдограф.
6. Дати визначення терміну орграф.
7. Пояснити поняття матриці суміжності та інциденцій.
8. Що таке частина графа, доповнення графа?
14.5 Приклади аудиторних і домашніх задач
1. Зобразити графи за матрицею суміжності S та матрицею інциденцій R:
2. Зобразити орграф і його матрицю інциденій за матрицею суміжності M:
3. Зобразити повний граф з 5 вершинами. Знайти його частини, які містять 1, 2, 3 та 4 ребра.
4. Знайти об’єднання та перетин графів, які задано матрицями інциденцій:
15 Практичне заняття № 13. Ейлерові і гамільтонові ланцюги і цикли
15.1 Мета заняття
Ознайомитися з поняттям ейлерових та гамільтонових ланцюгів і циклів, а також основними методами їхнього пошуку. Навчитися застосовувати отримані знання на практиці.
15.2 Методичні рекомендації до самостійної роботи студентів
Під час підготовки до практичного заняття необхідно вивчити відповідний розділ конспекту лекцій та ознайомитися з матеріалом підручників [1, c. 246-248, c. 304-322; 2, c. 246-248, c. 304-322; 4, c. 320-325; 8, c. 83-91; 12, c. 312-316, c. 350-353; 14, c. 53-77; 17, c. 64-128].
При повторенні матеріалу слід звернути увагу на такі питання:
теорема Ейлера;
алгоритм знаходження ейлерова циклу (ланцюга);
гамільтонові ланцюги і цикли;
умови існування гамільтонових ланцюгів і циклів на графі;
алгоритм Робертса-Флореса присутності на графі гамільтонових ланцюгів і циклів.