Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Теорема Куратовского

Читайте также:
  1. а)Определители 2-го,3-го и п-го порядков (определения и из св-ва). б)Теорема Лапласа о разложении определителя по элементам строки или столбца.
  2. Внешние эффекты и общественное благо. Теорема Коуза.
  3. Интегральная теорема Лапласа.
  4. Линии магнитной индукции. Поток вектора магнитной индукции. Теорема Гаусса для магнитного поля
  5. ЛОКАЛЬНАЯ ТЕОРЕМА ЛАПЛАСА
  6. Полные системы. Теорема Поста
  7. Полукольцо натуральных чисел и кольцо целых чисел. Теорема о делении с остатком. Наибольший общий делитель и наименьшее общее кратное двух чисел.
  8. Теорема (Абеля).
  9. Теорема Коши.( Коши (1789-1857)- французский математик)
  10. Теорема Кронекера-Капелли о совместности СЛУ.

Для формулировки теоремы введем сначала некоторые понятия.

Слиянием, или стягиванием двух ребер (u, v), (v, w), инцидентных вершине степени 2, называется операция, которая эти ребра заменяет одним ребром (u, w) и удаляет вершину v.

Разбиение ребра (u, w) называется операция, обратная слиянию, т. е. добавление новой вершины v степени 2 и замены ребра (u, w) парой ребер (u, v), (v, w).

Пример этих операций приведен на рисунках 7 и 8.

Переход от графа на рисунке 7 к графу на рисунке 8 – это стягивание, а переход от графа на рисунке 8 к графу на рисунке 7 – разбиение.

Как говорилось ранее, графы К3,3 и К5 являются не планарными, а отсюда можно сделать вывод, что и другие графы, изоморфные этим не будут планарными.

Для расширения наших возможностей по анализу планарности произвольного графа нам потребуется понятие, по сути, менее требовательное, или как говорят более «мягкое», чем изоморфизм. В самом деле, представим себе граф, который можно получить, например из графа К5 в результате деления одного из его ребер на два с помощью введения дополнительной вершины (валентности 2, например, в середине ребра). Ясно, что в результате так же получится не планарный граф, но он не будет изоморфен графу К5 (так как он имеет на одну вершину и на одно ребро больше, чем исходный). Граф, который можно получить таким образом мы назовем геоморфным. Итак, введем конкретное определение геоморфных графов.

Два графа называются геоморфными, если они изоморфны или могут быть сделаны изоморфными в результате конечного числа слияний и разбиений.

На рисунке 9 изображены два геоморфных графа. Для определения геоморфности двух графов Г и Ф следует последовательно удалить все вершины валентности 2 в каждом из графов. Пусть в результате этого получаются графы Г` и Ф`. Тогда графы Г и Ф геоморфные, если и только если Г` и Ф` изоморфные.

На рисунке 10 можно увидеть граф, полученный в результате удаления вершин валентности 2, из графов, показанных на рисунке 9. Графы являются изоморфными, следовательно графы, изображенные на рисунке 9 – геоморфные.




Дата добавления: 2015-01-30; просмотров: 17 | Поможем написать вашу работу | Нарушение авторских прав

1 | <== 2 ==> |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав