Регистрация Спросить otvet5GPT
gasi20022
25.07.2022 21:16
Информатика
Есть ответ 👍

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

150
179
Посмотреть ответы 2

Ответы на вопрос:

vcurakina
vcurakina
4,7(79 оценок)
Переформулируем на теорию графов: если все вершины графа разделить на два множества, то найдется ребро, соединяющее вершину одного множества с вершиной другого. доказать, что граф связный. докажем от противного. пусть граф несвязный, тогда у него есть как минимум две компоненты связности. тогда возьмем такое разбиение графа на группы: в перво й группе будут только вершины первой компоненты связности, а в другой группе будут все остальные вершины. в таком случае, по условию существует ребро из вершины первой группы в вершину второй, но это невозможно, так как вершины принадлежат к  разным компонентам связности, а по определению между двумя разными компонентами связности нет ребер. противоречие, следовательно, граф связный. что и требовалось доказать.
TheBrainPlay
TheBrainPlay
4,7(20 оценок)
128

Реши свою проблему, спроси otvet5GPT

  • Быстро
    Мгновенный ответ на твой вопрос
  • Точно
    Бот обладает знаниями во всех сферах
  • Бесплатно
    Задай вопрос и получи ответ бесплатно

Популярно: Информатика

Caktus Image

Есть вопросы?

  • Как otvet5GPT работает?

    otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.

  • Сколько это стоит?

    Проект находиться на стадии тестирования и все услуги бесплатны.

  • Могу ли я использовать otvet5GPT в школе?

    Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!

  • В чем отличия от ChatGPT?

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

Подпишись на наш телеграмм канал

GTP TOP NEWS