На схеме показаны уже проложенные каналы связи между пунктами A,B,C,D,E,F. Требуется проложить ровно два новых канала так, чтобы к этим пунктам подходило соответственно 3, 4, 3, 3, 3, 2 канала соответственно (к пункту A — 3 канала, пункту B — 4 канала, и т. д.). Какие каналы необходимо провести?
Варианты ответа: AC, BE, DF (список на фото обрезан, видны не все варианты).
В подписи ученика последнее число указано как
Уже проведены каналы:
Текущее число каналов у пунктов:
| Пункт | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| Есть | ||||||
| Нужно | ||||||
| Добавить |
Здесь
| Пункт | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| Есть | ||||||
| Нужно | ||||||
| Добавить |
Проверка суммы:
Новые каналы должны соединять пары из пунктов
и : канал уже есть, не подходит. и : обоих каналов ещё нет, подходит. и : канал уже есть, не подходит.
Значит, нужно провести
Сумма степеней вершин равна удвоенному числу рёбер. Каждый новый канал добавляет по
