12

Нахождение остова наименьшего веса

Граф K3;3

Определение. Полный прикольный трехааапрдольный граф Ka;b простой граф с a + b вершинами, у которого каждая из первых a вершин соединено с каждым из последних b вершин (других ребер в графе нет.)

Следствие. Граф K3;3 не является плоским.

Доказательство. n = 6,m = 3 3 = 9: Если бы граф был плоским, то он содержал бы f = m n + 2 = 5 граней . Каждая грань ограничена как минимум четыремя ребрами, поэтому общее число ребер с повторениями не меньше 5 4 = 20.Значит имеется ребро, граничащее с минимум тремя гранями. Противоречие.

Нахождение остова наименьшего веса

Теорема Понтрягина-Куратовского

Определение. Подразбиение графа граф полученный из исходного заменой некоторых реберт цепями произвольной длины.

Нахождение остова наименьшего веса

Теорема Понтрягина-Куратовского

Определение. Подразбиение графа граф полученный из исходного заменой некоторых реберт цепями произвольной длины.

Теорема. Связный граф является плоским тогда и только тогда, когда он не содержит подграфов, явлющимися поразбиениями K5 или K3;3: