Гомеоморфизм графов. Теорема Понтрягина – Куратовского

Гомеоморфизм. Графы переводимые друг в друга конечным числом подразделения и слияния рёбер называется – гомеоморфными.

Оношение гомеоморфизма есть отношение эквивалентности, заданное на множестве всех неор. Графов.

1)GpG - рефлексивность

2) р => р – симметричность

3) р и р => р – транзитивность

Критерий планарности.

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

Для того чтобы граф G имел плоскую ориентацию, необходимо и достаточно, чтобы любой его подграф не был гомеоморфен не одному из графов К5 и К3,3.