Заметил, что если в графе отсутствуют циклы длины 3, то он двудольный. Как это можно строго доказать?

задан 8 Июн '15 2:35

2

Это неверно. Контрпримером является контур пятиугольника.

Верно то, что граф двудольный тогда и только тогда, когда в нём нет никаких циклов нечётной длины. Это достаточно простая теорема.

(8 Июн '15 2:38) falcao

А можно ссылку на такую теорему, пожалуйста.

(8 Июн '15 2:40) dsarovsky

Она вообще-то доказывается очень коротко. Фиксируем вершину v, и все вершины делим на два класса -- по признаку чётности расстояния (длины кратчайшего пути) до v. Это даёт двудольный граф: соединение между вершинами одной "чётности" сразу даёт цикл нечётной длины. Который раскрасить в два цвета нельзя, то есть обратное тоже верно.

(8 Июн '15 4:32) falcao

Ссылку тоже можно. Вот, самая простая ссылка. https://ru.wikipedia.org/wiki/Двудольный_граф

(9 Июн '15 11:13) knop

Bipartite Graph - его еще называют двухцветным, потому что можно разделить на два множества разных цветов, так чтобы ни одна вершина из одного множества не имела общих ребер с никакой другой вершиной из того же множества. Кстати определить является ли граф двухцветным просто: берем исходную вершину, красим ее в синий цвет, далее всех соседей в красный, затем соседей соседей в синий и так далее. Если окажется, что среди соседних вершин есть хобя бы одна другого цвета, то граф не можеть быть двухцветным. Я помню, писал программку, которая это определяет.

(10 Июн '15 3:05) night-raven
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×654
×239

задан
8 Июн '15 2:35

показан
1133 раза

обновлен
10 Июн '15 3:05

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru