Задание 2. Неориентированный граф

8. Начертить граф по матрице длин дуг. Самостоятельно обозначить ребра.

9. Охарактеризовать граф.

10. Назвать специальные вершины и рёбра.

11. Рассчитать степени вершин.

12. Выписать матрицы смежности, инцидентности, достижимости, связности.

13. Выписать цикл, цепь, простой цикл, простую цепь.

14. Рассчитать ОД и МОД.

Решение:

1.граф:

2.неориентированный граф G=(V, X).

V={V0, V1, V2, V3, V4, V5, V6}; X={X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11}.

X0={V0, V0}, X1={V0, V4}, X2={V0, V5}, X3={V0, V6}, X4={V1, V2}, X5={V1, V3}

X6={V2, V3}, X7={V2, V4}, X8={V3, V4}, X9={V3, V6}, X10={V4, V5}, X11={V5, V6}

3.X0-петля, специальных вершин.

4.степени вершин:

(V0)=4; (V1)=2; (V2)=3; (V2)=3 (V3)=4; V4)=4; (V5)=3; (V6)=3

5.

Матрица идентичности

Матрица достижимости

Матрица связности

6.

Простой цикл: V0 X0 V0; цикл: V4 X1 V0 X0 V0 X2 V5 X10 V4

Простая цепь: V1 X4 V2; Цепь: V4 X1 V0 X0 V0 X2 V5.

7.

Остовное дерево и минимальное остовное дерево:

Остовным деревом графа называется связной подграф этого графа, содержащий все вершины графа, и не имеющий циклов.

Построение МОД:

Дейкстры-прима. крускала

1.V0, 2 V4V5,

V0 V4, V0V4

V4V5, V5V6,

V5V6, V1V2,

V4V4, V6V4

V3V1, V1V3

V1V2

1 Новиков, Ф.А. Дискретная математика для программистов. [Текст] / Ф.А. Новиков. – Спб.: Питер, 2006. – 364 с.: ил.

2 Поздняков, С.Н. Дискретная математика. [Текст] / С.Н. Поздняков, С.В. Рыбин. – М.: Академия, 2008. – 352 с.

3 Пономарев, В.Ф. Дискретная математика для инженеров. [Текст] / В.Ф. Пономарев. – М.: Горячая линия – Телеком, 2009. – 380 с.: ил.

4 Спирина, М.С. Дискретная математика: учебник. [Текст] / М.С. Спирина, П.А. Спирин. – М.: Академия, 2009. – 368 с.

Шапорев, С.Д. Дискретная математика. Курс лекций и практических занятий. [Текст] / С.Д. Шапорев. – Спб.: БХВ-Петербург, 2007. – 400 с.: ил