- •Лекція 1. Поняття неорієнтованого графу. Різновиди, способи подання та перетворення неорієнтованих графів Поняття неорієнтованого графу
- •Різновиди графів
- •Способи подання графів
- •Операції над графами та перетворення графів
- •Контрольні питання
- •Задачі та вправи
- •Лекція 2. Маршрути у неорієнтованому графі. Зв’язні графи Маршрут, ланцюг, цикл у неорієнтованому графі
- •Зв’язність графу
- •Способи перевірки зв’язності графу
- •Неорієнтовані графи та бінарні відношення
- •Контрольні питання
- •Задачі та вправи
- •Лекція 3. Ізоморфні графи Поняття ізоморфізму графів
- •Властивості ізоморфних графів
- •Контрольні питання
- •Задачі та вправи
- •Лекція 4. Неорієнтовані дерева та їх властивості Поняття неорієнтованого дерева
- •Властивості неорієнтованих дерев
- •Контрольні питання
- •Задачі та вправи
- •Лекція 5. Орієнтовані графи та орієнтовані дерева Поняття орієнтованого графу
- •Способи подання орієнтованих графів
- •Шляхи у орієнтованому графі
- •Поняття орієнтованого дерева
- •Контрольні питання
- •Задачі та вправи
- •Лекція 6. Алгоритми на графах Обходи орієнтованих дерев
- •Алгоритм Дейкстри обчислення вартостей найкоротших шляхів з одного джерела у орграфі
- •Алгоритм Крускала побудови кістякового дерева найменшої вартості
- •Контрольні питання
- •Задачі та вправи
- •Список використаної та рекомендованої літератури
Контрольні питання
Які графи називаються ізоморфними?
Що таке узгоджена перестановка рядків та стовпчиків матриці суміжності графу?
Які є необхідні умови ізоморфності графів?
Які є необхідні та достатні умови ізоморфності скінченних графів?
Які є способи перевірки ізоморфності: а) довільних графів, б) скінченних графів?
а) |
б) |
|
|
в) | |
|
|
г) | |
|
|
д) | |
Рис. 9 |
Задачі та вправи
I. Побудувати такі неізоморфні графи G1=(V1,E1) та G2=(V2,E2), що |V1|=|V2|, |E1|=|E2|.
II. Визначити, які з пар графів, поданих на рис.10-13, є ізоморфними, а які – ні.
| ||||
а) |
б) |
|
а) |
б) |
Рис. 10 |
|
Рис. 11 |
| ||||
а) |
б) |
|
а) |
б) |
Рис. 12 |
|
Рис. 13 |
ІІІ. Перевірити, чи є ізоморфними графи G та Н. Якщо графи ізоморфні, довести це, використавши теореми 4 та 5.
1) G=({1,2,3,4,5,6},{(1,2),(1,3),(3,2),(2,4),(3,4),(4,1),(4,5),(5,6),(6,1),(6,2),(5,1),(5,2)}), H=({1,2,3,4,5,6},{(1,2),(1,3),(1,4),(1,5),(1,6),(2,5),(2,6),(3,5),(3,4),(4,5),(4,6),(5,6)});
2) G=({1,2,3,4,5,6,7},{(1,2),(1,3),(3,6),(6,4),(4,2),(4,7),(5,7),(2,5),(1,4),(6,7)}), H=({a,b,c,d,e,f,g},{(a,b),(a,c),(a,d),(b,d),(b,e),(d,e),(e,g),(g,f),(f,c),(d,f)});
3) G=({1,2,3,4,5},{(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(1,4),(1,5)}), H=({a,b,c,d,e},{(a,b),(a,c),(a,d),(b,c),(a,e),(b,d),(b,e),(d,e),(c,d)});
4) G=({1,2,3,4,5,6},{(1,2),(1,3),(2,4),(2,3),(4,1),(2,5),(2,6),(4,6),(3,6),(3,5),(1,5),(1,6)}), H=({a,b,c,d,e,f},{(a,b),(a,c),(c,d),(c,b),(a,d),(d,e),(b,e),(b,f),(e,f),(f,a),(a,e),(b,d)});
5) G=({1,2,3,4,5,6,7},{(1,2),(1,3),(3,4),(3,5),(2,3),(2,4),(4,5),(5,6),(6,4),(6,7),(6,1), (1,7),(7,2),(7,5)}), H=({a,b,c,d,e,f,g},{(a,b),(a,e),(b,c),(c,f),(c,d),(d,a),(a,g),(g,d), (d,e),(e,b),(e,f),(f,g),(f,b),(g,c)});
6) G=({1,2,3,4,5,6,7,8},{(1,2),(2,3),(1,4),(3,5),(4,6),(4,2),(6,7),(7,8),(7,5),(8,5)}), H=({a,b,c,d,e,f,g,h},{(a,b),(a,c),(b,d),(c,e),(e,f),(f,g),(d,g),(g,h),(h,d),(c,f)});
7) G=({1,2,3,4,5,6},{(4,2),(4,3),(2,1),(2,3),(4,1),(2,5),(2,6),(1,6),(3,6),(3,5),(4,5),(4,6)}), H=({a,b,c,d,e,f},{(a,b),(a,c),(a,f),(b,f),(a,d),(a,e),(d,e),(b,e),(b,c),(e,c),(b,d),(f,d)});
8) G=({1,2,3,4,5,6},{(1,2),(2,3),(3,4),(4,5),(4,6),(5,6),(5,3),(5,2),(5,1),(6,1),(6,2),(6,3)}), H=({a,b,c,d,e,f},{(a,b),(b,c),(c,a),(a,f),(d,e),(c,d),(b,f),(b,d),(a,e),(a,d),(d,f),(e,f)});
9) G=({1,2,3,4,5,6,7,8},{(1,2),(1,4),(1,5),(2,3),(2,6),(3,4),(3,7),(4,8),(5,6),(6,7),(7,8),(5,8)}), H=({1,2,3,4,5,6,7,8},{(1,2),(3,4),(5,6),(7,8),(8,6),(3,1),(1,7),(3,5),(6,4),(8,2),(4,2),(5,7)});
10) G=({1,2,3,4,5,6},{(1,2),(3,4),(1,5),(2,6),(3,5),(3,6),(1,6),(2,5)}), H=({1,2,3,4,5,6},{(1,2),(1,3),(1,5),(4,2),(4,6),(4,5),(2,6),(3,5)}).
ІV. Довести, що якщо графи G1=(V1,E1) та G2=(V2,E2) ізоморфні, то для будь-якого цілого невід’ємного числа k кількість вершин степеня k в обох графах однакова.
V. Довести, що якщо графи G1=(V1,E1) та G2=(V2,E2) ізоморфні, то для будь-якого цілого невід’ємного числа k кількість простих циклів довжини k в обох графах однакова.
VІ. Довести, що графи G1=(V1,E1) та G2=(V2,E2) ізоморфні тоді й тільки тоді, коли ізоморфні їх доповнення.
VІІ. Нехай на множині графів визначено бінарне відношення R: GRH графи G та H ізоморфні. Довести, що R є відношенням еквівалентності.