Задание по матрицам

Задание 22

Дана матрица смежности мультиграфа . Задайте граф с помощью матрицы инцидентности, структурой смежности, списком дуг. Изобразите граф.

1		2
3		4
5		6
7		8
9		10
11		12

13		14
15		16
17		18
19		20
21		22
23		24
25		28

Задание 23

Для графов ииз ТР  №9 постройте граф:

полученный удалением вершины 2 из ; полученный из  отождествлением двух неинцидентных вершин (на выбор); из  стягиванием дуги (на выбор); ; +; .

Задание 24

Дана матрица инцидентности графа . Задайте граф с помощью матрицы смежности, структурой смежности, списком дуг. Изобразите граф.

Найдите всевозможные подграфы графа и укажите какие из них изоморфны.  Найдите все попарно неизоморфные части графа .

1		2		3
4		5		6
7		8		9
10		11		12
13		14		15
16		17		18
19		20		21
22		23		24
25		28

Задание 25

Найдите хроматическое число графа G из ТР  №10. Является ли граф гамильтоновым? Если да, то укажите гамильтонов цикл.

Задание 26

Орграф задан матрицей смежности. Требуется:

а) нарисовать граф;  б) выделить компоненты сильной связности;

в) в соответствующем неорграфе найти эйлерову цепь (или цикл).

1 ;  2 ; 3 ;  4 ;  5 ;  6 ; 7 ;  8 ; 9 ; 10 ;  11 ; 12 ;13 ;14 ; 15 ; 

16 ;17 ;18 ;19 ; 20;  21 ;22;23;24;25; 26;27;28;29;30. 

Задание 27

Дана матрица весов взвешенного графа .

Изобразите граф. Постройте матрицу инцидентности графа G, используя веса ребер в качестве их номеров. Найдите остов минимального веса, матрицы фундаментальных циклов и разрезов относительно выбранного остова. Определиите хроматическое число графа G. Является ли граф G гамильтоновым? Если да, то укажите гамильтонов цикл. Найдите толщину графа G. Найдите эйлерову цепь (или цикл) графа G, если они существуют. С помощью алгоритма Форда-Беллмана найдите наилегчайшие маршруты из вершины 1 до всех остальных.

1		2
3		4
5		6
7		8
9		10
11		12
13		14
15		16
17		18
19		20
21		22
23		24
25		28