Гамма-алгоритм — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Задача |definition=Определить, является ли граф планарным, и, если да, произвести его плоскую ...»)
 
Строка 5: Строка 5:
  
 
Чтобы проверить планарность графа и произвести его плоскую укладку, удобно пользоваться гамма-алгоритмом.
 
Чтобы проверить планарность графа и произвести его плоскую укладку, удобно пользоваться гамма-алгоритмом.
 +
 +
= Входные данные =
 +
 +
На вход алгоритму подаются графы со следующими свойствами:
 +
# Граф связный,
 +
# Граф содержит хотя бы один цикл,
 +
# Граф не имеет [[Мост, эквивалентные определения|мостов]].
 +
 +
Если нарушено свойство <tex>1</tex>, то граф нужно укладывать отдельно по компонентам связности. Если нарушено свойство <tex>2</tex>, то граф {{---}} дерево и нарисовать его плоскую укладку тривиально.
 +
 +
Более подробно рассмотрим случай, когда в графе <tex>G</tex> нарушено свойство <tex>3</tex>. Сначала все мосты нужно убрать, далее произвести отдельную укладку всех компонент следующим образом: уложим одну компоненту связности, а следующую компоненту, связанную с первой в графе <tex>G</tex> мостом, будем рисовать в той грани, в которой лежит вершина, принадлежащая мосту. Иначе может сложиться ситуация, когда концевая вершина моста будет находиться внутри плоского графа, а следующая компонента - снаружи. Таким образом мы сможем соединить мостом нужные вершины. Далее будем так поступать с каждой новой компонентой.

Версия 22:30, 19 ноября 2015

Задача:
Определить, является ли граф планарным, и, если да, произвести его плоскую укладку.

Существует теорема Понтрягина-Куратовского, которая говорит, что граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных [math] K_{5} [/math] или [math] K_{3, 3} [/math]. Но этот критерий очень трудно проверить на практике, поэтому данная теорема представляет лишь теоретический интерес.

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

Входные данные

На вход алгоритму подаются графы со следующими свойствами:

  1. Граф связный,
  2. Граф содержит хотя бы один цикл,
  3. Граф не имеет мостов.

Если нарушено свойство [math]1[/math], то граф нужно укладывать отдельно по компонентам связности. Если нарушено свойство [math]2[/math], то граф — дерево и нарисовать его плоскую укладку тривиально.

Более подробно рассмотрим случай, когда в графе [math]G[/math] нарушено свойство [math]3[/math]. Сначала все мосты нужно убрать, далее произвести отдельную укладку всех компонент следующим образом: уложим одну компоненту связности, а следующую компоненту, связанную с первой в графе [math]G[/math] мостом, будем рисовать в той грани, в которой лежит вершина, принадлежащая мосту. Иначе может сложиться ситуация, когда концевая вершина моста будет находиться внутри плоского графа, а следующая компонента - снаружи. Таким образом мы сможем соединить мостом нужные вершины. Далее будем так поступать с каждой новой компонентой.