yourdomain.com

доказать что для любого графа c вершинами сумма вершиного покрытия графа и вершиное покрытие его дополнения больше или равно

M	Нарушение последних трёх пунктов правил, тема закрыта.

A	Нарушение последних трёх пунктов правил, тема закрыта.

Хотел подсказать dfi, но не успел
A задачка-то симпатичная!
Уважамые модераторы! Можно ли пообсуждать ee на форуме (просто так, безотносительно вопроса dfi?)

M	Тема открыта

A	Тема открыта

VAL писал(а):Source of the post
Хотел подсказать dfi, но не успел
A задачка-то симпатичная!
Уважамые модераторы! Можно ли пообсуждать ee на форуме (просто так, безотносительно вопроса dfi?)

Судя по всему, можно

Тогда напомню, что вершинным покрытием графа G называется подмножество вершин графа такое, что каждое ребро графа инцидентно хотя бы одно вершине из этого подмножества. Наименьшее возможное число вершин в покрытии называется числом (вершинного) покрытия и обозначается .
Граф дополнительный к G - это граф, определенный на том же множестве вершин, что и G, по правилу: пара вершин образует ребро в дополнительном графе тогда и только тогда, когда она не образует ребра в исходном.
Полагаю, наиболее скучная часть решения изложена. Жду предложений по содержательной части.

VAL писал(а):Source of the post
Тогда напомню, что вершинным покрытием графа G называется подмножество вершин графа такое, что каждое ребро графа инцидентно хотя бы одно вершине из этого подмножества. Наименьшее возможное число вершин в покрытии называется числом (вершинного) покрытия и обозначается .
Граф дополнительный к G - это граф, определенный на том же множестве вершин, что и G, по правилу: пара вершин образует ребро в дополнительном графе тогда и только тогда, когда она не образует ребра в исходном.

Ну вот, dfi пропал (подтвердив характеристику "странник"). Другие форумчане тоже не заинтересовались задачкой. Ho, реанимировав тему. я взял на себя некие оьязательства (она, как бы, уже моя, не dfi). Поэтому привожу решение.

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