VAL писал(а):Source of the post Тогда напомню, что вершинным покрытием графа G называется подмножество вершин графа такое, что каждое ребро графа инцидентно хотя бы одно вершине из этого подмножества. Наименьшее возможное число вершин в покрытии называется числом (вершинного) покрытия и обозначается
.
Граф дополнительный к G - это граф, определенный на том же множестве вершин, что и G, по правилу: пара вершин образует ребро в дополнительном графе тогда и только тогда, когда она не образует ребра в исходном.
Ну вот,
dfi пропал (подтвердив характеристику "странник"). Другие форумчане тоже не заинтересовались задачкой. Ho, реанимировав тему. я взял на себя некие оьязательства (она, как бы, уже моя, не
dfi). Поэтому привожу решение.
Пусть
и
- наименьшие покрытия исходного и дополнительного графов. Тогда
. Это значит, что существуют, по крайней мере, 2 вершины, не входящие ни в одно из покрытий. Эта пара вершин обязательно образует ребро либо в исходном, либо в дополнительном графе, которое в любом случае оказывается непокрытым. Противоречие.
Последний раз редактировалось
VAL 30 ноя 2019, 08:44, всего редактировалось 1 раз.
Причина: test