|
Известно, что в неориентированном графе существует путь, проходящий по каждому ребру ровно два раза. Верно ли, что в графе есть эйлеров цикл? задан 14 Ноя '17 16:12 
jonasina |
|
Пусть дан конечный связный граф. Произведём с ним операцию удвоения рёбер. Это значит, что для каждого ребра e мы добавляем его "двойник" e' с теми же концевыми вершинами. (При этом, если две точки соединяло k рёбер, то их станет 2k.) Такой граф всегда окажется эйлеровым, так как степени всех вершин станут чётными. В нём есть эйлеров цикл. Далее, если мы проходили по ребру e' (в каком-то из направлений), то будем проходить по e. Это значит, что в исходном графе можно всегда пройти дважды по каждому ребру. Значит, достаточно взять в качестве контрпримера любой не эйлеров граф -- например, квадрат с диагональю. отвечен 14 Ноя '17 17:09 
falcao |