Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 28 ]  На страницу Пред.  1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Re: Задача о закрытых рейсах
СообщениеДобавлено: 27 июл 2018, 13:32 
Не в сети
Одарённый
Зарегистрирован:
30 окт 2015, 02:45
Сообщений: 132
Cпасибо сказано: 7
Спасибо получено:
2 раз в 2 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Решение использует тот факт, что если взять пару авиакомпаний, то каждый компонент связности в графе можно представить в виде круга. А в таком графе удаление одного ребра не влияет на количество компонент связности. Т.е. если мы могли добраться из одного города в другой, то сможем и после удаления одного рейса

Наверное, именно здесь и не понимаю.

А что касается первого предложения решения?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача о закрытых рейсах
СообщениеДобавлено: 27 июл 2018, 13:35 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Volodislavir писал(а):
А что касается первого предложения решения?

Volodislavir, давайте вы не будете отсылать на что-то, а в цитате указывать текст что непонятен

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача о закрытых рейсах
СообщениеДобавлено: 27 июл 2018, 13:36 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Volodislavir писал(а):
Наверное, именно здесь и не понимаю.

Что именно?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача о закрытых рейсах
СообщениеДобавлено: 27 июл 2018, 13:43 
Не в сети
Одарённый
Зарегистрирован:
30 окт 2015, 02:45
Сообщений: 132
Cпасибо сказано: 7
Спасибо получено:
2 раз в 2 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Volodislavir писал(а):
Наверное, именно здесь и не понимаю.

Что именно?

Как данная конструкция может служить доказательством.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача о закрытых рейсах
СообщениеДобавлено: 27 июл 2018, 13:54 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Ну вот смотрите.
У нас был путь из Х в Y. Пусть на этом пути закрыт рейс из А в Б. Пусть этот рейс принадлежит авиакомпании 1. Мы берем авиакомпанию 0 без закрытых рейсов. Такая есть.
И рисуем граф, в котором есть только эти две авиакомпании. В этом графе из каждой вершины выходит два ребра. Это возможно только если в каждой компоненте связности города расположены по кругу: [math]a_1 \to a_2 \to \ldots \to a_n \to a_1[/math], [math]b_1 \to b_2 \to \ldots \to b_k \to b_1[/math] и т.д.
Если в этом графе удалить одно ребро, то мы можем пройти в другую сторону. А значит есть другой путь из А в Б, принадлежащий компаниям 1 и 0. Им и воспользуемся.
А поскольку А и Б у нас произвольны, то мы можем "заменить" любой закрытый рейс.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю swan "Спасибо" сказали:
Volodislavir
 Заголовок сообщения: Re: Задача о закрытых рейсах
СообщениеДобавлено: 27 июл 2018, 13:59 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Volodislavir писал(а):
Как данная конструкция может служить доказательством.


Вполне себе конструктивное доказательство. Показываем, как получить путь из любого города в другой.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача о закрытых рейсах
СообщениеДобавлено: 27 июл 2018, 14:05 
Не в сети
Одарённый
Зарегистрирован:
30 окт 2015, 02:45
Сообщений: 132
Cпасибо сказано: 7
Спасибо получено:
2 раз в 2 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Ну вот смотрите.
У нас был путь из Х в Y. Пусть на этом пути закрыт рейс из А в Б. Пусть этот рейс принадлежит авиакомпании 1. Мы берем авиакомпанию 0 без закрытых рейсов. Такая есть.
И рисуем граф, в котором есть только эти две авиакомпании. В этом графе из каждой вершины выходит два ребра. Это возможно только если в каждой компоненте связности города расположены по кругу: [math]a_1 \to a_2 \to \ldots \to a_n \to a_1[/math], [math]b_1 \to b_2 \to \ldots \to b_k \to b_1[/math] и т.д.
Если в этом графе удалить одно ребро, то мы можем пройти в другую сторону. А значит есть другой путь из А в Б, принадлежащий компаниям 1 и 0. Им и воспользуемся.
А поскольку А и Б у нас произвольны, то мы можем "заменить" любой закрытый рейс.

Ага.
Вот, я привёл пример конкретного графа
Изображение
Пусть А крайне левая вершина, а Б крайне правая. Пусть на пути АБ закрыт рейс (12) и как мы это дело обойдём?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача о закрытых рейсах
СообщениеДобавлено: 27 июл 2018, 14:11 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Вы не указали авиакомпании

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача о закрытых рейсах
СообщениеДобавлено: 27 июл 2018, 14:13 
Не в сети
Одарённый
Зарегистрирован:
30 окт 2015, 02:45
Сообщений: 132
Cпасибо сказано: 7
Спасибо получено:
2 раз в 2 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Вы не указали авиакомпании

(12) - рейс третьей авиакомпании, которая закрыла этот рейс.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача о закрытых рейсах
СообщениеДобавлено: 27 июл 2018, 14:19 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Пронумеруйте все города от 1 до 10 и укажите все рейсы каждой авиакомпании

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

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Теория вероятности: задача про шары и задача про точку

в форуме Теория вероятностей

AdmiralAnanas

6

484

02 окт 2021, 01:43

Задача на построение. Корректна ли задача?

в форуме Геометрия

Student Studentovich

9

663

19 июл 2020, 19:17

Задача

в форуме Дискретная математика, Теория множеств и Логика

Owl1337

1

495

27 ноя 2014, 15:05

Задача

в форуме Алгебра

oksi

1

532

24 ноя 2014, 21:18

Задача

в форуме Механика

ANASTASIA9999

3

609

24 ноя 2014, 18:19

Задача №15

в форуме Интересные задачи участников форума MHP

andrei

8

1197

02 мар 2017, 14:45

Задача

в форуме Дискретная математика, Теория множеств и Логика

Sweet_blood

1

327

21 ноя 2014, 23:27

Задача по ТВ

в форуме Теория вероятностей

351w

3

734

04 фев 2019, 16:45

Задача по ТВ

в форуме Теория вероятностей

351w

1

398

03 фев 2019, 20:59

Задача

в форуме Теория вероятностей

viktorinka

3

529

03 мар 2017, 14:55


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 19


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved