Свободные деревья

Упражнения

1. Построить пример графов G₁ и G₂, для которых p₁ = p₂, q₁ = q₂, d₁ = d₂, D ₁ = D ₂, но G₁ ~ G₂.

2. Построить граф по матрице смежности:

.

8. Построить граф по матрице смежности:

.

9. Построить граф по матрице инцидентности:

.

10. Построить граф по матрице инцидентности:

.

11. Построить граф по списку пар вершин: ({1,4}, {2,4}, {1,2}, {2,4}).

12. Построить граф по списку пар вершин: ((2,2), (4,1), (4,2), (3,4)).

13. Построить неориентированный граф по списку списков: ((2,4,5), (1,4), (4), (1,2,3), (2)).

14. Построить орграф по списку списков: ((2,1), (2,4), (4,3), Æ, (2,3,4)).

Глава 7. Деревья и циклы

Граф без циклов называется ациклическим, или лесом. Связный ациклический граф называется (свободным) деревом. Таким образом, компонентами связности леса являются деревья.

В связном графе G выполняется неравенство q (G) ³ p (G)–1. Граф G, в котором q (G) = p (G) - 1, называется древовидным.

В ациклическом графе G z (G) = 0. Пусть и, v — несмежные вершины графа G, х = (и, v) Ï Е. Если граф G + х имеет только один простой цикл, z (G + х) = 1, то граф G называется субциклическим.

Пример

На рис. 7.1 показаны диаграммы всех различных (свободных) деревьев с 5 вер­шинами, а на рис. 7.2 — диаграммы всех различных (свободных) деревьев с 6 вершинами.

Рис. 7.1.Свободные деревья с 5 вершинами

Рис. 7.2. Свободные деревья с 6 вершинами

Дата добавления: 2014-12-27