Построение 20 новых городов на 9 островах можно представить в виде задачи о связях между вершинами графа. Вершины графа представляют острова, а ребра графа – паромные сообщения между городами.
Для решения задачи определим минимальное количество ребер, необходимых для связывания всех городов на разных островах.
Если на каждом острове будет построен по одному городу, то количеством ребер будет равно 9 – каждый город на острове соединен прямым сообщением с остальными.
Однако, нам нужно построить 20 городов, поэтому некоторые острова должны быть связаны между собой несколькими ребрами.
Предположим, что на 9 островах построены по одному городу, а оставшиеся 11 городов распределены по ним так, чтобы на каждом острове был хотя бы один город. Это означает, что придется соединить острова с дополнительными ребрами.
Должен быть хотя бы один город, который соединен с каждым другим городом. Давайте построим такого города на одном из островов и соединим его с каждым городом на других островах. Таким образом, у нас будет 10 ребер (городов) связывающих этот город со всеми остальными.
Теперь остается 10 городов, которые нужно распределить по островам так, чтобы был как минимум один на каждом острове. Мы можем просто разместить по одному городу на каждом острове и соединить их друг с другом. В результате мы получим 9 дополнительных ребер.
Итак, минимальное количество паромных сообщений, необходимых для связи 20 городов на 9 островах, равно 10 + 9 = 19.