|
Докажите, что если есть граф $%G$% и его дополнительный граф $%G$%, то один из них обязательно связный. Под дополнительным графом я подразумеваю такой граф, в котором соединены те вершины, которых нет в основном графе. задан 13 Ноя '14 2:41 
gagarin
показано 5 из 7
показать еще 2
|
|
Индукция по числу вершин. Все рёбра полного графа раскрашены в красный или синий цвет. Для графа с одной вершиной, а также с двумя, всё очевидно. Рассмотрим одну из вершин графа и временно удалим её со всеми инцидентными ей рёбрами. Получится полный подграф на $%n-1$% вершине, и там по предположению индукции или красный подграф связен, или синий. Оба случая аналогичны; без ограничения общности предположим первое. Если удаляемая вершина соединена красным ребром хотя бы с одной из остальных, то получается связный подграф из красных рёбер. Если это не так, то все её соединения синие, и уже такой подграф будет синим связным подграфом. Добавление. В комментариях уже не осталось места, а мне так и не удалось, к большому сожалению, убедить автора вопроса в простой мысли, что красный и синий цвет здесь обладают полной симметрией. Поэтому специально для автора пишу текст примерно вдвое длиннее, чтобы вопросов больше не оставалось. Предыдущий текст не убираю, чтобы можно было сравнить. Индукция по числу вершин. Все рёбра полного графа раскрашены в красный или синий цвет. Для графа с одной вершиной, а также с двумя, всё очевидно. Рассмотрим одну из вершин графа и временно удалим её со всеми инцидентными ей рёбрами. Получится полный подграф на $%n-1$% вершине, и там по предположению индукции или красный подграф связен, или синий. Рассмотрим два случая. 1) В полном графе с $%n-1$% вершиной имеется связный подграф из рёбер красного цвета. Если удаляемая вершина соединена красным ребром хотя бы с одной из остальных, то получается связный подграф из красных рёбер. Если это не так, то все её соединения синие, и уже такой подграф будет синим связным подграфом. 2) В полном графе с $%n-1$% вершиной имеется связный подграф из рёбер синего цвета. Если удаляемая вершина соединена синим ребром хотя бы с одной из остальных, то получается связный подграф из синих рёбер. Если это не так, то все её соединения красные, и уже такой подграф будет красным связным подграфом. отвечен 13 Ноя '14 2:47 
falcao @Алексей авт: мы раскрашиваем не вершины, а рёбра -- прочитайте внимательно! Раскраска рассматривается любая, это равноценно рассмотрению подграфа и дополнительного подграфа. Все красные рёбра входят в подграф, все синие -- в дополнение. Это просто язык, на котором удобнее рассуждать.
(13 Ноя '14 3:02)
falcao
Да не получается. Хорошо. Возьмем тот же квадрат. Раскрасим красным только боковым стороны. Удаляем верхнюю левую вершину, т.е. удаляем одно красное ребро и два синих. Удаляемая вершина соединена красным ребром с другой вершиной. Но граф из красных ребер не связный! Почему?
(13 Ноя '14 3:07)
gagarin
@Алексей авт: когда Вы удаляете вершину с рёбрами, то далее ищете в оставшейся части связный одноцветный подграф. По предположению индукции, он всегда есть. Какой именно -- красный или синий, мы не знаем. Но между цветами имеет место полная симметрия. Поэтому в решении был рассмотрен только случай, когда этот подграф будет красным. Если он синий, то надо второй раз повторить то же самое с переменой цветов. Обычно так не делают, потому что нет смысла дважды излагать одно и то же. В Вашем примере имеется синий подграф на трёх вершинах, и тогда, конечно, мы ищем синее соединение с ним. Оно есть.
(13 Ноя '14 3:13)
falcao
@Алексей авт: давайте введём обозначения. Вы брали квадрат ABCD. Первая вершина верхняя левая, далее всё по часовой стрелке. Боковые рёбра AD, BC красные. Всё остальное синее, включая диагонали (граф полный). Удаляем A. Остаётся треугольник BCD. В нём есть связный синий подграф из BD и CD, его и берём. Нам ведь надо только, чтобы из каждой вершины можно было добраться в каждую по рёбрам одного цвета. В конце A синим подсоединяем в B, вот и всё.
(13 Ноя '14 3:25)
falcao
Если удаляемая вершина соединена красным ребром хотя бы с одной из остальных, то получается связный подграф из красных рёбер. У нас получается синий граф связный. Как? Удаляемая вершина А соединена красным ребром с Д. И мы говорим, что красный граф связный, хотя по условия красный граф это ребра АД и ВС.
(13 Ноя '14 3:28)
gagarin
@Алексей авт: я ведь этот момент уже объяснил, а Вы снова к нему вернулись. У меня в тексте сказано, что на n-1 есть красный ИЛИ синий подграф -- это так и есть. Я далее ПРЕДПОЛАГАЮ, что он красный (это не всегда так; в Вашем примере он синий). Если предположение верно, то я соединяю n-ю вершину красным ребром. Если предположение неверно, то верно всё то же с заменой красного на синий и наоборот. Этот случай полностью аналогичен. Если подграф на n-1 вершине был синий, то надо повторить рассуждение с взаимной заменой слов "синий" и красный.
(13 Ноя '14 3:44)
falcao
Я не понимаю. Можно еще раз с самого начала очень и очень подробно. Прошу. Очень нужно. Пожалуйста. Вот у вас написано: Если удаляемая вершина соединена красным ребром хотя бы с одной из остальных, то получается связный подграф из красных рёбер. Да у нас удаляемая вершина А соединена красным ребром АД с другой вершиной и вы утвеждаете, что подграф красный - связный. Но у нас не так. Я вот это не понимаю.
(13 Ноя '14 4:06)
gagarin
показано 5 из 7
показать еще 2
|
Я не понимаю. С чем мы соединяем n-у вершину? У вас неправильно написано Если удаляемая вершина соединена красным ребром хотя бы с одной из остальных, то получается связный подграф из красных рёбер. Если это не так, то все её соединения синие, и уже такой подграф будет синим связным подграфом.
И красный подграф в нашем случае, кстати, тоже связан ВС.
@Алексей авт: я сделал добавление, чтобы было понятнее. У меня всё написано правильно. Вершина с номером $%n$% изначально была соединена в полном графе с каждой из остальных вершин. Это часть условия задачи.
Вернемся к нашей задаче. У нас квадрат. Удаляем А. Остается связный подграф синего цвета с вершинами ВСД. Мы видим, что удаляемая вершина соединена синим ребром с двумя оставшимися вершинами. Значит что мы должны соединить? Вы имеете виду, когда говорите "Если удаляемая вершина соединена красным ребром хотя бы с одной из остальных, то получается связный подграф из красных рёбер." О нашем первоначальном синим подграфе или о подграфе, который получился при удалении вершины? (Как я понимаю, вы имеете ввиду первоначальный.)
@Алексей авт: это случай из пункта 2, см. Добавление. Мы нашли связный синий подграф на n-1 вершине (в примере n=4), а нам нужен связный одноцветный подграф на n вершинах. Что для этого достаточно, чтобы n-я точка попадала в такой подграф? Если у неё есть хотя бы одно синее ребро, соединяющее его с какой-то из n-1 оставшихся вершин (например, AB), то добавляем его в подграф, и он оказывается связным. То, что там синим является ещё и ребро AC, ничему не мешает, так как добавление новых рёбер к связному подграфу оставляет его связным.
Все. Я понял. Спасибо. Просто нехорошо разобрался в определениях связный граф и полный граф.
Я правильно понимаю, что связный граф не обязательно должен быть циклом? Ну или хотя бы замкнут.
@Алексей авт: можно просто повторить определения. Граф называется простым, если в нём нет петель и кратных рёбер. Простой граф называется полным, если любые две его вершины соединены ребром. У циклического графа число вершин конечно, и они соединены по циклу. Связным называется такой граф, в котором любые две вершины можно соединить хотя бы одним путём, состоящим из рёбер (то есть он не распадается на части). Связных графов намного больше, чем циклов. Понятия замкнутого графа не существует.