Для неорієнтованого графу G, зображеного на рисунку, виконати вказані операції видалення вершин та ребер.

ТЕМА: ТЕОРІЯ ГРАФІВ

Завдання 1

Для неорієнтованого графу G, зображеного на рисунку, виконати вказані операції видалення вершин та ребер.

Побудувати отриманий граф. Скласти матрицю суміжності на матрицю інцидентності. Написати маршрут, ланцюг, простий ланцюг, цикл, простий цикл. Знайти:

а) число вершин і число ребер;

б) степені всіх вершин;

в) центр, периферійні вершини, радіус і діаметр;

г) точки зчленування і мости.

№ в-ту

Видалити в графі G

вершини {i}

Видалити в графі G

ребра {(i,j)}

{1;3}

{(7;10);(10;11);(10;13)}

{3;13}

{(6;7);(7;8);(10;11)}

{5;9}

{(6;10);(10;11);(11;13)}

{9;11}

{(4;7);(4;8);(10;13)}

{8;10}

{(4;7);(9;12);(12;13)}

{10;12}

{(2;6);(8;9);(7;11)}

{10;11}

{(4;7);(4;8);(9;12)}

{4;13}

{(6;10);(10;11);(11;12)}

{8;12}

{(5;6);(6;7);(10;13)}

{8;13}

{(6;7);(9;12);(11;12)}

{1;3}

{(6;7);(7;10);(10;11)}

{2;3}

{(4;8);(6;7);(10;11)}

{4;5}

{(1;2);(6;10);(11;13)}

{5;9}

{(1;4);(4;7);(10;13)}

{2;8}

{(3;7);(4;7);(12;13)}

{3;10}

{(2;5);(2;6);(7;11)}

{5;10}

{(1;4);(4;7);(9;12)}

{3;4}

{(2;5);(6;10);(11;12)}

{1;8}

{(2;7);(5;6);(10;13)}

{2;8;13}

{(3;7);(6;7);(9;12);(11;12)}

Завдання 2

Для заданого графу побудувати:

а) матрицю суміжності;

б) матрицю інцидентності;

в) список ребер

г) знайти степені вершин графа.

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

Завдання 3

Необхідно з’єднати дев’ять міст нафтопроводом. Можливі з’єднання і вартість будівництва вказана Для неорієнтованого графу G, зображеного на рисунку, виконати вказані операції видалення вершин та ребер. в таблиці. Як з’єднати всі міста, щоб побудувати самий дешевий нафтопровід? Результат зобразити у вигляді графу.

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

Задача 4.

Знайти мінімальний та максимальний шляхи, що поєднують вхід та вихід графа, попередньо вірно пронумерувавши вершини.

1.

2.

3.

4.

5.

6.



7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.


Дата добавления: 2015-10-21; просмотров: 4 | Нарушение авторских прав


documentaepwnph.html
documentaepwuzp.html
documentaepxcjx.html
documentaepxjuf.html
documentaepxren.html
Документ Для неорієнтованого графу G, зображеного на рисунку, виконати вказані операції видалення вершин та ребер.