Города соединены авиалиниями. Известно, как бы ни разделить города на две группы, всегда найдется авиалиния, соединяющая какой-нибудь город одной группы с каким-то городом второй группы. Доказать на графах что можно перелететь из любого города страны в любой другой город
297
ОТВЕТЫ
Переформулируем задачу на теорию графов:
Если все вершины графа разделить на два множества, то найдется ребро, соединяющее вершину одного множества с вершиной другого. Доказать, что граф связный.
Докажем от противного. Пусть граф несвязный, тогда у него есть как минимум две компоненты связности. Тогда возьмем такое разбиение графа на группы: в первой группе будут только вершины первой компоненты связности, а в другой группе будут все остальные вершины. В таком случае, по условию задачи существует ребро из вершины первой группы в вершину второй, но это невозможно, так как вершины принадлежат к разным компонентам связности, а по определению между двумя разными компонентами связности нет ребер. Противоречие, следовательно, граф связный. Что и требовалось доказать.
Если все вершины графа разделить на два множества, то найдется ребро, соединяющее вершину одного множества с вершиной другого. Доказать, что граф связный.
Докажем от противного. Пусть граф несвязный, тогда у него есть как минимум две компоненты связности. Тогда возьмем такое разбиение графа на группы: в первой группе будут только вершины первой компоненты связности, а в другой группе будут все остальные вершины. В таком случае, по условию задачи существует ребро из вершины первой группы в вершину второй, но это невозможно, так как вершины принадлежат к разным компонентам связности, а по определению между двумя разными компонентами связности нет ребер. Противоречие, следовательно, граф связный. Что и требовалось доказать.
6
Отв. дан
Arashisida
Для написания вопросов и ответов необходимо зарегистрироваться на сайте
Другие вопросы в разделе - Физика
Ygg
Помогите, виписати з художньої літератури 2 фрагменти з прямою ...
2018-09-23 00:00:00
Makelv
За 2.5 с прямолинейного равноускоренного движения тело прошло 40 ...
2018-09-23 00:00:00
Илья
Найдите наибольшее двух значное число и наименьшее трехзначное число, ...
2018-09-23 00:00:00
Cordasida
Десятичный код "2" = 50.Kакой двоичный код y "7"? ...
2018-09-23 00:00:00