Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 2 из 3 |
[ Сообщений: 28 ] | На страницу Пред. 1, 2, 3 След. |
|
Автор | Сообщение | |
---|---|---|
Volodislavir |
|
|
swan писал(а): Решение использует тот факт, что если взять пару авиакомпаний, то каждый компонент связности в графе можно представить в виде круга. А в таком графе удаление одного ребра не влияет на количество компонент связности. Т.е. если мы могли добраться из одного города в другой, то сможем и после удаления одного рейса Наверное, именно здесь и не понимаю. А что касается первого предложения решения? |
||
Вернуться к началу | ||
swan |
|
|
Volodislavir писал(а): А что касается первого предложения решения? Volodislavir, давайте вы не будете отсылать на что-то, а в цитате указывать текст что непонятен |
||
Вернуться к началу | ||
swan |
|
|
Volodislavir писал(а): Наверное, именно здесь и не понимаю. Что именно? |
||
Вернуться к началу | ||
Volodislavir |
|
|
swan писал(а): Volodislavir писал(а): Наверное, именно здесь и не понимаю. Что именно? Как данная конструкция может служить доказательством. |
||
Вернуться к началу | ||
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. Им и воспользуемся. А поскольку А и Б у нас произвольны, то мы можем "заменить" любой закрытый рейс. |
||
Вернуться к началу | ||
За это сообщение пользователю swan "Спасибо" сказали: Volodislavir |
||
swan |
|
|
Volodislavir писал(а): Как данная конструкция может служить доказательством. Вполне себе конструктивное доказательство. Показываем, как получить путь из любого города в другой. |
||
Вернуться к началу | ||
Volodislavir |
|
|
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) и как мы это дело обойдём? |
||
Вернуться к началу | ||
swan |
|
|
Вы не указали авиакомпании
|
||
Вернуться к началу | ||
Volodislavir |
|
|
swan писал(а): Вы не указали авиакомпании (12) - рейс третьей авиакомпании, которая закрыла этот рейс. |
||
Вернуться к началу | ||
swan |
|
|
Пронумеруйте все города от 1 до 10 и укажите все рейсы каждой авиакомпании
|
||
Вернуться к началу | ||
На страницу Пред. 1, 2, 3 След. | [ Сообщений: 28 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Теория вероятности: задача про шары и задача про точку
в форуме Теория вероятностей |
6 |
484 |
02 окт 2021, 01:43 |
|
Задача на построение. Корректна ли задача?
в форуме Геометрия |
9 |
663 |
19 июл 2020, 19:17 |
|
Задача | 1 |
495 |
27 ноя 2014, 15:05 |
|
Задача
в форуме Алгебра |
1 |
532 |
24 ноя 2014, 21:18 |
|
Задача
в форуме Механика |
3 |
609 |
24 ноя 2014, 18:19 |
|
Задача №15 | 8 |
1197 |
02 мар 2017, 14:45 |
|
Задача | 1 |
327 |
21 ноя 2014, 23:27 |
|
Задача по ТВ
в форуме Теория вероятностей |
3 |
734 |
04 фев 2019, 16:45 |
|
Задача по ТВ
в форуме Теория вероятностей |
1 |
398 |
03 фев 2019, 20:59 |
|
Задача
в форуме Теория вероятностей |
3 |
529 |
03 мар 2017, 14:55 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 19 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |