Задача 099 — Задачи на Графы

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

Подсказка

Отметим в нашем графе $G$ любую вершину $a$ и построим дерево поиска в глубину $T$ с корнем $a$ .

Решение

Отметим в нашем графе $G$ любую вершину $a$ и построим дерево поиска в глубину $T$ с корнем $a$ .

Пронумеруем вершину $a$ числом 0 и будем добавлять в дерево и нумеровать вершины по следующему принципу: если в дереве есть вершины с номерами от 1 до $k$ , то рассмотрим вершину с наибольшим номером, из которой выходит хотя бы одно ребро в вершину, не принадлежащую уже построенному дереву, добавим любое из таких рёбер в дерево, и новой вершине присвоим номер $k+1$ . Все ребра дерева $T$ ориентируем от меньшего номера к большему.

Пусть $t(x)$ — номер вершины $x$ при построении дерева $T$ . Докажем, что все требования задачи выполняются. Очевидно, в остовном дереве графа на 2009 вершинах как раз 2008 ребер, так что мы поставили 2008 стрелочек. Пусть $u v$ — ребро исходного графа $G$ , причем $t(u)<t(v)$ . Если $u v$ входит в $T$ , всё в порядке. В противном случае вершина $v$ подвешена в $T$ к вершине $v_{1} \neq u$ . Так как в графе $G$ вершина $v$ смежна с $u$ , то по построению дерева $t\left(v_{1}\right)>t(u)$ , и $t(v)>t\left(v_{1}\right)$ . Рассмотрим момент, когда добавлялась вершина $v_{1}$ . Так как в этот момент в дереве еще нет смежной с $u$ вершины $v$ , то по построению вершина $v_{1}$ подвешена в $T$ к вершине $v_{2}$ , где $t\left(v_{1}\right)>t\left(v_{2}\right) \geq t(u)$ . И так далее, пока очередная вершина $v_{m}$ не окажется совпадающей с $u$ (это случится, потому что номера $t\left(v_{i}\right)$ монотонно убывают, и все они не меньше, чем $t(u)$ ). Искомый путь $u=v_{m} \rightarrow v_{m-1} \rightarrow \ldots \rightarrow v_{1} \rightarrow v$ построен.