Дано: полный граф на 16 вершинах
Найти: минимальное число маршрутов в графе, которые в совокупности содержат все его ребра и все вершины
Решение:
В полном графе на n вершинах всего рёбер будет \(C_{n}^{2}\) (то есть количество сочетаний из n по 2). Для графа на 16 вершинах это будет \(C_{16}^{2} = \frac{16*15}{2} = 120\) рёбер.
Так как каждое ребро должно быть пройдено дважды (раз в каждом направлении), общее количество рёбер в маршрутах будет равно 240.
Поэтому минимальное число маршрутов, которые в совокупности содержат все рёбра и все вершины, будет равно 15, так как для каждой вершины потребуется 15 рёбер, чтобы пройти через все остальные вершины.
Ответ: Минимальное число маршрутов в графе, которые в совокупности содержат все его рёбра и все вершины, равно 15.