9.1.1. Определения

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

ЗАМЕЧАНИЕ

Прилагательное «свободное» употребляется в том случае, когда нужно подчеркнуть от­личие деревьев от других объектов, родственных деревьям: ориентированных деревьев, упорядоченных деревьев и т. д.

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

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

Пример

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

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

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