Для неорієнтованого графу 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

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

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