Решение. Матрица смежности несимметричная, поэтому граф ориентированный

Решение.

Матрица смежности несимметричная, поэтому граф ориентированный. Количество вершин – 6. Строим граф. Из вершины 1 ведут дуги в вершины 2 и 3; из вершины 2 – в вершины 3 и 6; из вершины 3 – в вершину 4; из вершины 4 – в вершины 1, 5 и 6; из вершины 5 – в вершину 2; из вершины 6 – в вершину 1. Проверить правильность построения можно, посчитав полустепени исхода (сумма цифр по строке) и полустепени захода (сумма цифр по столбцу) для каждой вершины. Граф, соответствующий матрице смежности (табл. 5), изображен на рис. 5.

Рисунок 5 – Граф

Задание 5. По матрице инциденций (табл. 6) построить граф и определить, является ли он ориентированным или неориентированным.

Таблица 6 – Матрица инциденций графа

	a	b	c	d	e	f	g

В матрице инциденций нет значений (-1), потому можно сделать вывод о том, что граф неориентированный. Количество вершин равно 6, количество ребер – 7. Строим пустой граф на шести вершинах и соединяем их ребрами: ребро а соединяет вершины 1 и 4, ребро b – вершины 2 и 4, и т.д. Граф, соответствующий матрице инциденций (табл. 6), изображен на рис. 6.

Рисунок 5 – Граф

Задача 5. Определить, является ли для графа соответствующий маршрут цепью, простой цепью, циклом, простым циклом, если маршрут: :

1) ;

2) ;

3) ;

4) ;

5) .

Решение. Согласно определению получим:

1) простой цикл (все вершины и ребра различны);

2) цикл (все ребра различны, а вершины нет);

3) простая цепь;

4) маршрут (есть одинаковые ребра и вершины);

5) простая цепь.

Задание 6. Для графов и на рисунке 6 выполнить операции объединения, пересечения и композиции и .

Рисунок 6 – Графы и

Дата добавления: 2014-11-20