Задача №2 В трех различных домах живут три поссорившиеся между собой соседа. Недалеко от их домов имеются три колодца. Можно ли от каждого дома проложить к каждому из колодцев тропинку так, чтобы никакие две из них не пересекались?
Решение:
Мы имеем 3 дома и 3 колодца, а согласно условию из каждого дома нужно провести тропинку к каждому колодцу. Это означает, что между домами и колодцами нужно провести все возможные соединения, то есть у нас получается полный двудольный граф K₍₃,₃₎, состоящий из 3 + 3 = 6 вершин и 9 ребер.
Шаг 1. Постановка задачи в терминах графа.