Условие:
Какие утверждения верны?
(1) Любое совершенное паросочетание является максимальным.
(2) В любой чередующейся цепи число светлых ребер на единицу больше числа темных.
(3) Если у дерева есть совершенное паросочетание, то число его вершин четно.
Ответ дайте в формате последовательности 0 и 1 (например, 001): на первом месте запишите 1, если утверждение (1) верное, в противном случае запишите 0; на втором месте запишите 1, если утверждение (2) верное, в противном случае запишите 0; и т.д.
Решение:
Мы разберём каждое утверждение по порядку. ----------------------------------------------------------- Утверждение (1): «Любое совершенное паросочетание является максимальным.» 1. Совершенное паросочетание – это паросочетание, покрывающее все вершины графа. 2. Максимальное паросочетание – это паросочетание наибольшей мощности (то есть не существует паросочетания с большим числом рёбер в данном графе). 3. Если паросочетание совершенное, то число его рёбер равно половине числа вершин графа. Добавить ещё одно ребро нельзя, ведь оно бы соприкоснулось с вершиной, уже покрытой ребром. 4. Значит, с...