Образуют ли зелёные ребра графа на рисунке путь?
Путь в графе из вершины \(\displaystyle А\) в вершину \(\displaystyle В\) – это последовательность ребер, такая что
- первое ребро начинается в вершине \(\displaystyle А{ \small ,}\)
- каждое следующее начинается в конце предыдущего,
- последнее заканчивается в вершине \(\displaystyle В{\small .}\)
\(\displaystyle А\) называется началом пути, \(\displaystyle В\) – концом.
Посмотрим на вершину \(\displaystyle E {\small,}\) которая принадлежит только одному зеленому ребру, поэтому не может являться одновременно концом одного ребра и началом другого. Значит, \(\displaystyle E\) может быть только началом или концом пути.
Пусть \(\displaystyle E\) – начало пути.
Из вершины \(\displaystyle E\) по зелёному ребру мы можем "дойти" только в вершину \(\displaystyle D{ \small ,}\) из которой не выходит ни одного зелёного ребра, кроме того, по которому мы в нее пришли.
Значит, построить путь из всех зелёных рёбер не удастся.
Было замечено, что вершина, которая принадлежит лишь одному зелёному ребру, может быть только концом или началом пути.
Таких вершин на рисунке четыре: \(\displaystyle E{ \small ,}\,D{ \small ,}\,B{ \small ,}\,F{ \small .}\)
Но у пути может быть только одно начало и один конец.
Ответ: Нет.