УПРАЖНЕНИЯ. 2. Покажите, что в орграфе без контуров всегда есть вершина нулевой полустепенью захода и вершина с нулевой полустепенью исхода

1. Докажите теоремы 65.1 и 65.2.

2. Покажите, что в орграфе без контуров всегда есть вершина нулевой полустепенью захода и вершина с нулевой полустепенью исхода.

3. Докажите, что пара векторов (З², 2) и (3, 2², 1) является графической, и постройте ее реализацию.

4. Постройте ориентированный граф, для которого вектор (3³, 2²) является как списком полустепеней исхода вершин, так и списком полустепеней захода вершин.

5. Докажите, что следующие свойства орграфа G эквивалентны:

1) G — бесконтурный граф;

2) граф G и его конденсация G* изоморфны;

3) каждый маршрут орграфа G является путем;

4) вершины орграфа G можно упорядочить так, что его матрица смежности будет верхней треугольной матрицей.

6. Полустепень исхода вершины турнира называется количеством очков вершины. Докажите, что в любом турнире расстояние от вершины с максимальным количеством очков до любой другой вершины равно 1 или 2.

7. Докажите, что в транзитивном турнире существует ровно одингамильтонов путь.

8. Докажите, что ребра любого неориентированного графа можно так ориентировать, что в полученном орграфе |d⁺(v) — d^-(v) |<=1 для любой вершины v.

9. Покажите, что любой турнир либо является сильным, либо может быть превращен в сильный сменой ориентации только одной дуги.

10. Докажите, что неориентированный граф G является ос­нованием некоторого сильного орграфа тогда и только тогда, ког­да G связен и не имеет мостов.

11. Транзитивным замыканием орграфа G называется орграф G’, для которого VG’ = VG, а (и, v) G’ тогда и только тогда, ког­да в орграфе G вершина v достижима из и. Транзитивная редук­ция орграфа G определяется как орграф с наименьшим числом дуг, транзитивное замыкание которого совпадает с транзитивным замы­канием орграфа G. Покажите, что если орграф не имеет конту­ров, то его транзитивная редукция единственна.

12. Пусть G — орграф без петель с п вершинами и m дугами. Докажите, что если G является связным, но не сильным орграфом, то п — 1 <= m <= (п — 1)², а если G — сильный орграф, то п<=m<= п<=(п — 1).

13. Докажите, что в орграфе порядка п, для любых двух не­смежных вершин и и v которого верно неравенство d(u)+ d(v) >= 2п — 3, существует гамильтонов путь.

14. Орграф L(G), вершины которого соответствуют дугам ор­графа G и (и, v) AL(G) тогда и только тогда, когда соответст­вующие дуги порождают в G маршрут, называется реберным ор­графом. Выразите число вершин и число дуг реберного орграфа L(G) через аналогичные параметры орграфа G.

15. Целочисленная функция g(v)>=0, v VG, называется функцией Гранди орграфа G, если для любой вершины v значение g(v) совпадает с минимальным из тех неотрицательных целых чи­сел, которые не принадлежат множеству {g(u): и Г(у)}. Покажи­те, что если каждый подграф орграфа G обладает ядром, то сущест­вует функция Гранди орграфа G.