Сабақ Тақырыбы: Цикломатикалық сан. Хроматикалық сан. Графтардағы жолдарды және ең қысқа жолдарды анықтау. Тапсырмалар

В терминах орграфов можно дать точное определение структурам данных, известным как ориентированное дерево.

Ориентированное дерево Т = (V, E) — это ациклический орграф, в котором одна вершина v_r V не имеет предков, а каждая другая

вершина имеет только одного непосредственного предка; v_r называется корнем дерева. Бинарное дерево — это ориентированное дерево, в котором каждая вершина имеет не более двух

непосредственных по- томков, т. е. δ⁺( v)≤2 для всех v V. Говорят, что бинарное дерево является полным, если каждая вершина, не являющаяся листом, имеет ровно два непосредственных потомка.

Утверждение. Следующие утверждения эквивалентны по отношению к орграфу G = (V, Е):

а) G является деревом.

б) Граф F(G) связный, и существует вершина v_r, которая не имеет предков, а все другие вершины имеют только по одному непосредственному предку.

в) G имеет вершину v_r, которая соединяется с любой другой вершиной единственным маршрутом.

г) G имеет вершину v_r, которая