2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Обход Москвы
Сообщение03.02.2019, 10:24 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: Обход Москвы
Сообщение03.02.2019, 11:05 


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

 Профиль  
                  
 
 Re: Обход Москвы
Сообщение03.02.2019, 12:02 
Аватара пользователя


01/12/11

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

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

 Профиль  
                  
 
 Re: Обход Москвы
Сообщение03.02.2019, 12:20 
Заслуженный участник
Аватара пользователя


31/01/14
11292
Hogtown
wrest в сообщении #1373745 писал(а):
Москву (город) вообще нельзя обойти проходя по улицам, она не односвязная.
Пожалуйста, посмотрите определение односвязной области

 Профиль  
                  
 
 Re: Обход Москвы
Сообщение03.02.2019, 12:34 


05/09/16
12038
Red_Herring в сообщении #1373772 писал(а):
Пожалуйста, посмотрите определение односвязной области

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

 Профиль  
                  
 
 Re: Обход Москвы
Сообщение03.02.2019, 13:32 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Обход Москвы
Сообщение03.02.2019, 14:02 
Аватара пользователя


11/12/16
13811
уездный город Н
Ktina в сообщении #1373737 писал(а):
Докажите, что Москву можно обойти, пройдя по всем улицам ровно два раза.


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

 Профиль  
                  
 
 Re: Обход Москвы
Сообщение03.02.2019, 14:02 


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

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

 Профиль  
                  
 
 Re: Обход Москвы
Сообщение03.02.2019, 14:09 
Аватара пользователя


01/11/14
1896
Principality of Galilee
wrest в сообщении #1373809 писал(а):
Что вообще считать улицей?
wrest
Ребро графа.
Поскольку в условии требуется обойти каждое ребро дважды, то количество рёбер умножаем на $2$, а, значит, степени всех вершин чётные. А значит, перед нами эйлеров граф, в котором существует эйлеров цикл. Осталось только найти его (хотя бы алгоритмом Флёри) и отправляться в путь. По-моему, так.
Да, ну и понятно, что граф связный.

 Профиль  
                  
 
 Re: Обход Москвы
Сообщение03.02.2019, 14:28 
Заслуженный участник


20/08/14
11687
Россия, Москва
А по моему можно проще: рекурсивно обходить поддеревья с возвратом обратно по ребру если натыкаемся на уже посещённую вершину.

 Профиль  
                  
 
 Re: Обход Москвы
Сообщение03.02.2019, 16:10 
Аватара пользователя


01/12/11

8634
EUgeneUS в сообщении #1373808 писал(а):
Ktina в сообщении #1373737 писал(а):
Докажите, что Москву можно обойти, пройдя по всем улицам ровно два раза.


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

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

 Профиль  
                  
 
 Re: Обход Москвы
Сообщение03.02.2019, 18:04 
Аватара пользователя


11/12/16
13811
уездный город Н
Ktina
О необходимом и достаточном ("тогда и только тогда ...").

 Профиль  
                  
 
 Re: Обход Москвы
Сообщение03.02.2019, 18:44 
Аватара пользователя


01/12/11

8634
EUgeneUS в сообщении #1373886 писал(а):
Ktina
О необходимом и достаточном ("тогда и только тогда ...").

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


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

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

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

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

 Профиль  
                  
 
 Re: Обход Москвы
Сообщение03.02.2019, 18:49 
Аватара пользователя


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

 Профиль  
                  
 
 Posted automatically
Сообщение03.02.2019, 23:05 


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

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

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

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


-- 04.02.2019, 01:07 --

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: dgwuqtj


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group