Планарный граф↵
↵
Планарный граф — граф который можно изобразить на плоскости без пересечения ребер (кроме как в вершинах). Существует критерий планарности: граф планарен тогда и только тогда, когда он не содержит подграфы $K_5$ и $K_3,_3$. Где $K_5$ — полный граф на 5 вершинах, $K_3,_3$ полный двудольный граф на 6 вершинах (по 3 в каждой доле).↵
↵
Формула Эйлера↵
↵
Если граф на $V$ вершинах с $E$ ребрами планарен, то количество граней, на которые граф разбивает плоскость $F = E - V + 2$. Попробуйте доказать самостоятельно.
↵
Планарный граф — граф который можно изобразить на плоскости без пересечения ребер (кроме как в вершинах). Существует критерий планарности: граф планарен тогда и только тогда, когда он не содержит подграфы $K_5$ и $K_3,_3$. Где $K_5$ — полный граф на 5 вершинах, $K_3,_3$ полный двудольный граф на 6 вершинах (по 3 в каждой доле).↵
↵
Формула Эйлера↵
↵
Если граф на $V$ вершинах с $E$ ребрами планарен, то количество граней, на которые граф разбивает плоскость $F = E - V + 2$. Попробуйте доказать самостоятельно.
