АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

ТЕОРЕМА 5.3

Прочитайте:
  1. Внешние эффекты. Теорема Коуза
  2. Внешние эффекты. Теорема Коуза
  3. Зовнішні ефекти. Теорема Коуза
  4. Мережі, потоки в мережах. Теорема Форда - Фалкерсона
  5. Поток вектора напряженности электростатического поля. Теорема Гаусса для электростатического поля в вакууме
  6. Сложение ускорений (теорема Кориолиса)
  7. Теорема
  8. ТЕОРЕМА 1.4
  9. Теорема о СНФ

(Критерий планарности Понтрягина-Куратовского)

Граф G является плоским или планарным тогда и только тогда, когда он не содержит подграфов, гомеоморфных графам K 3,3 или A 5.

 

Следовательно, планарность или непланарность произвольного графа G зависит от того, содержится ли в G подграф, стягиваемый к K 3,3 и A 5 или нет.

 

Для каждого графа G существует ровно две альтернативы:

1)граф имеет плоскую реализацию;

2) граф содержит подграф, гомеоморфный K 3,3 или A 5.

Поэтому решение вопроса о планарности произвольного графа G всегда может быть получено либо построением плоской реализации G, либо нахождением такого подграфа G, который гомеоморфен одному из графов K 3,3 или A 5.

При этом проверить наличие или отсутствие в G подграфов, стягиваемых к K 3,3 или A 5, можно путем перебора всех подграфов этого графа.

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

 

Пример. Граф, приведенный на рис. 5.10 не является плоским:

a

1 2

B c

 

Рис. 5.10

Этот граф является непланарным, поскольку в нем содержится подграф, гомеоморфный K 3,3. На приведенном рисунке выделены вершины, соответствующие вершинам K 3,3.

 

 
 

 


Рис. 5.11

Граф на рис. 5.11 является планарным, поскольку он может быть изображен как

 

 


 

 

Рис. 5.12

На рис. 5.11. и 5.12. изображен один и тот же граф. При этом закрашенная точка – это вершина графа, которая на этих рисунках размещается по-разному.

 

Замечание. При нахождении подграфов, гомеоморфных K 3,3 или A 5, необходимо учитывать, что разбиения разных ребер в K 3,3 или A 5 должны представляться в непланарных графах цепочками ребер, не имеющими общих элементов, в том числе вершин. Совпадения элементов допускаются только для крайних элементов таких цепочек, соответствующих вершинам K 3,3 или A 5.

 

Дата добавления: 2015-09-27 | Просмотры: 428 | Нарушение авторских прав

При использовании материала ссылка на сайт medlec.org обязательна! (0.003 сек.)