На декартовой плоскости нужно указать связный планарный граф (см. рисунок), затратив наименьшее возможное количество проволоки. Проволоку можно гнуть под любым углом и склеивать в точках соединения. Какое минимальное количество дуг должна включать модель, показанную на рисунке?

Question

Вопрос:

На декартовой плоскости нужно указать связный планарный граф (см. рисунок), затратив наименьшее возможное количество проволоки. Проволоку можно гнуть под любым углом и склеивать в точках соединения. Какое минимальное количество дуг должна включать модель, показанную на рисунке?

Ответ:

ФИО:Телефон:Емаил:Полное описание сути нарушения прав (почему распространение данной информации запрещено Правообладателем):

Accepted Answer

В изображённом графе 12 вершин. Для связного планарного графа с двумя и более вершинами минимальное число рёбер равно \(n-1\): это число рёбер связного дерева.

Следовательно, минимально возможное количество дуг:

\[12-1=11.\]

Ответ: 11.