Обход Москвы

[Ktina]

Докажите, что Москву можно обойти, пройдя по всем улицам ровно два раза.

[wrest]

Ktina
Москву (город) вообще нельзя обойти проходя по улицам, она не односвязная.

[Ktina]

wrest в сообщении #1373745 писал(а):

Ktina
Москву (город) вообще нельзя обойти проходя по улицам, она не односвязная.

В таком случае как доказать её неодносвязность?

[Red_Herring]

wrest в сообщении #1373745 писал(а):

Москву (город) вообще нельзя обойти проходя по улицам, она не односвязная.

Пожалуйста, посмотрите определение односвязной области

[wrest]

Red_Herring в сообщении #1373772 писал(а):

Пожалуйста, посмотрите определение односвязной области

Спасибо большое! Поправляюсь: Москва точно не является связной (а не неодносвязной).
Неодносвязной является Московская область (по крайней мере Зеленоградский АО -- анклав).

[waxtep]

Можно, хотя мероприятие может быть небезопасным. Техника прохождения одного из участков демонстрируется здесь (Ленинград/Дороги)

[EUgeneUS]

Ktina в сообщении #1373737 писал(а):

Докажите, что Москву можно обойти, пройдя по всем улицам ровно два раза.

Вам известен признак графа, который можно обойти ровно один раз?

[wrest]

Ну допустим, что мы не берем в учет несвязность Москвы, и рассматртваем каждую область по отдельности.
Тогда вопрос, а связная ли уличная сеть в каждрй из этих областей. Мне ответ на этот вопрос неизвестен. Например, есть ли такие улицы на островах, к которым нет мостов? Являются ли любые мосты частью улиц? Есть ли такие улицы, к которым нельзя пройти по улицам с любых улиц? Что вообще считать улицей?

В общем, Ktina, если вы хотели спросить "можно ли обойти связный граф пройдя по каждому ребру ровно два раза", то помойму, в итоге вы спросили не то.
Если вы хотели спросить "является ли уличная сеть Москвы связным графом", то ответ - "нет, не является".

[Gagarin1968]

wrest в сообщении #1373809 писал(а):

Что вообще считать улицей?

wrest
Ребро графа.
Поскольку в условии требуется обойти каждое ребро дважды, то количество рёбер умножаем на $2$, а, значит, степени всех вершин чётные. А значит, перед нами эйлеров граф, в котором существует эйлеров цикл. Осталось только найти его (хотя бы алгоритмом Флёри) и отправляться в путь. По-моему, так.
Да, ну и понятно, что граф связный.

[Dmitriy40]

А по моему можно проще: рекурсивно обходить поддеревья с возвратом обратно по ребру если натыкаемся на уже посещённую вершину.

[Ktina]

EUgeneUS в сообщении #1373808 писал(а):

Ktina в сообщении #1373737 писал(а):

Докажите, что Москву можно обойти, пройдя по всем улицам ровно два раза.

Вам известен признак графа, который можно обойти ровно один раз?

Вы о необходимом или о достаточном признаке?

[EUgeneUS]

Ktina
О необходимом и достаточном ("тогда и только тогда ...").

[Ktina]

EUgeneUS в сообщении #1373886 писал(а):

Ktina
О необходимом и достаточном ("тогда и только тогда ...").

Вот этот?

Цитата:

Граф называется полуэйлеровым, если он содержит эйлеров путь, но не содержит эйлеров цикл.

Более чёткая постановка задачи:

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

Попытка решения:

Если в графе нечётных вершин нет, можно доказать возможность обхода по индукции.
А вот если нечётные вершины имеются... там будет посложнее.

[EUgeneUS]

нет, конечно. Это определение, а не признак.
Когда ("тогда и только тогда...") существует эйлеров путь?

[Lia]

Тема перемещена из форума «Загадки, головоломки, ребусы» в форум «Карантин»
по следующим причинам:

По просьбе ТС.

Замечу, что задача нуждается в четкой постановке, формализации, ну и попытках решения, само собой.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

-- 04.02.2019, 01:07 --

Ktina
Для редактирования доступно только Ваше последнее сообщение.