![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Гомеоморфизм. Графы переводимые друг в друга конечным числом подразделения и слияния рёбер называется – гомеоморфными.
Оношение гомеоморфизма есть отношение эквивалентности, заданное на множестве всех неор. Графов.
1)GpG - рефлексивность
2) р
=>
р
– симметричность
3) р
и
р
=>
р
– транзитивность
Критерий планарности.
Теорема Пантрягина-Куратовского.
Для того чтобы граф G имел плоскую ориентацию, необходимо и достаточно, чтобы любой его подграф не был гомеоморфен не одному из графов К5 и К3,3.
Дата публикования: 2015-02-22; Прочитано: 419 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!