ГДЗ по вероятности и статистике, 10 класс, Высоцкий, номер 110: *. Эйлерова характеристика

В любом плоском графе сумма степеней всех областей равна удвоенному количеству рёбер. Это связано с тем, что каждое ребро является границей ровно двух областей (или дважды одной области в случае мостов/петель, но для простых связных графов это правило сохраняется).

Дано:

• 5 областей степени 4;
• 4 области степени 3.

Найдём сумму степеней всех областей:

Так как эта сумма равна 2E, где E — количество рёбер, то:

Итак, в графе 16 рёбер .

Формула Эйлера для связного плоского графа связывает количество вершин (V), рёбер (E) и областей (F):

Сначала определим общее количество областей F. В условии сказано про внутренние области, но в формуле Эйлера учитывается также внешняя неограниченная область. Однако, обычно под «областями» в таких задачах подразумевают все грани, включая внешнюю, либо нужно проверить контекст. Давайте посчитаем количество граней, указанных в условии: 5+4=9. Если это все грани, то F=9. Но часто в задачах на эйлерову характеристику подразумевается, что перечислены только ограниченные области, а внешняя — одна дополнительная. Проверим оба варианта или стандартную трактовку.

Стандартная трактовка: «область» в плоском графе — это компонента связности дополнения к графу на плоскости. Их количество обозначается F. В условии дано 5 областей степени 4 и 4 области степени 3. Всего областей F=5+4=9.

Подставим известные значения в формулу Эйлера:

Итак, в графе 9 вершин .

Проверим согласованность данных. У нас есть V=9, E=16, F=9. Формула Эйлера: 9-16+9=2. Верно.

Также можно проверить среднюю степень вершины. Сумма степеней вершин равна 2E=32. Средняя степень вершины 32/9≈3.55. Это допустимо для простого графа (средняя степень меньше 2(V-1)/V≈1.8? Нет, верхняя граница для планарного графа E≤3V-6. Проверим: 16≤3(9)-6=21. Неравенство выполняется, значит такой планарный граф может существовать.