Задания для самостоятельного решения:

Задание №1

Задать данный граф матрицами смежности и инцедентности.

Задание №2

Для данного графа (см. задание №1) вычислить хроматическое число h(T).

Варианты заданий:

Вариант №1	Вариант №2
Вариант №3	Вариант №4
Вариант №5	Вариант №6
Вариант №7	Вариант №8

Вариант №9 B	Вариант №10
Вариант №11	Вариант №12
Вариант №13	Вариант №14 E F
Вариант №15	Вариант №16

Вариант №17 C	Вариант №18
Вариант №19 C	Вариант№20

Практическая работа №10

Тема: Маршруты, циклы, связность.

Задание №1

По заданной матрице смежности определить число маршрутов длины 3 между любой парой вершин в графе:

	A	B	C	D
A	0	1	0	1
B	1	0	1	1
C	0	1	0	0
D	1	1	0	0

Восстановить маршрут из вершины С в вершину А.

Решение:

Вычислим последовательно степени матрицы S.

Из полученной матрицы S³ следует, что имеется два (A-A)-маршрута длины 3, четыре (B-A)-маршрута длины 3, один (C-A)-маршрут длины 3, три (D-A)-маршрута длины 3, т.е. число в (i, j) ячейке определяет количество маршрутов длины 3 из i-ой вершины в j-ую вершину.

Восстановим (C-A)-маршрут: элемент , равный единице, был получен в результате умножения элементов и , в свою очередь элемент получился путем умножения и . Тем самым, в формировании элемента участвовали элементы , и матрицы смежности, поэтому (C-A)-маршрут есть последовательность вершин (C, B, D, A).

Задание №2

По заданной матрице определить сильные компоненты связности графа:

	A	B	C	D	E
A	0	1	1	0	0
B	1	0	1	0	0
C	1	1	0	1	0
D	0	0	1	0	1
E	0	0	0	1	0

Решение:

Максимальная степень, в которую надо возвести матрицу смежность для определения сильных компонент связности равна диаметру графа. Для данного графа диаметр равен 3. Возведём матрицу смежности в 3 степень:

Компоненте сильной связности в матрице достижимости соответствует подматрица максимального размера, каждый элемент которой не равен 0. В данной матрице можно выделить три подматрицы: , (2), (2).

Это значит, что граф, описанный матрицей смежности имеет три сильные компоненты: {A, B, C}, {D}, {E}.