Дан полный граф с вершинами 1,2,3,4,5,6. Укажите, являются указанные множества ребер паросочетаниями или нет: (1) 12,34,56 (2) 25 (3) 12,34,54 (4) 12,56,24,35 Ответ дайте в формате последовательности 0 и 1 (например, 0011): на первом месте запишите 1,

6 ноября 2025
Высшая математика

Условие:

Дан полный граф с вершинами 1,2,3,4,5,6. Укажите, являются указанные множества ребер паросочетаниями или нет:
(1) 12,34,56
(2) 25
(3) 12,34,54
(4) 12,56,24,35

Ответ дайте в формате последовательности 0 и 1 (например, 0011): на первом месте запишите 1, если множество (1) является паросочетанием, в противном случае запишите 0 ; на втором месте запишите 1, если множество (2) является паросочетанием, в противном случае запишите 0; и т.д.

Решение:

Рассмотрим каждое множество ребер по отдельности. Напомним, что паросочетание – это такое множество ребер, что никакие два ребра не имеют общей вершины. 1. Множество (1): {12, 34, 56} • Ребро 12 соединяет вершины 1 и 2. • Ребро 34 соединяет вершины 3 и 4. • Ребро 56 соединяет вершины 5 и 6. Все ребра имеют различные вершины, никаких общих вершин нет. ...