Визуализация графов: left-right алгоритм распознавания планарности
Download as PPTX, PDF0 likes775 views
More Related Content
More from Alex Dainiak (20)
Визуализация графов: left-right алгоритм распознавания планарности
- 1. Визуализация графов Computer Science клуб, март 2014 Александр Дайняк, ФИВТ МФТИ www.dainiak.com
- 2. DFS-дерево и обратные рѐбра При поиске в глубину рёбра графа разбиваются на два типа: • рёбра DFS-дерева (в «новые» вершины), • обратные рёбра (в пройденные вершины).
- 3. DFS-дерево и обратные рѐбра При поиске в глубину рёбра графа разбиваются на два типа: • рёбра DFS-дерева (в «новые» вершины), • обратные рёбра (в пройденные вершины).
- 4. DFS-дерево и обратные рѐбра При поиске в глубину рёбра графа разбиваются на два типа: • рёбра DFS-дерева (в «новые» вершины), • обратные рёбра (в пройденные вершины).
- 5. DFS-дерево и обратные рѐбра При поиске в глубину рёбра графа разбиваются на два типа: • рёбра DFS-дерева (в «новые» вершины), • обратные рёбра (в пройденные вершины).
- 6. DFS-дерево и обратные рѐбра При поиске в глубину рёбра графа разбиваются на два типа: • рёбра DFS-дерева (в «новые» вершины), • обратные рёбра (в пройденные вершины).
- 7. DFS-дерево и обратные рѐбра При поиске в глубину рёбра графа разбиваются на два типа: • рёбра DFS-дерева (в «новые» вершины), • обратные рёбра (в пройденные вершины).
- 8. DFS-дерево и обратные рѐбра При поиске в глубину рёбра графа разбиваются на два типа: • рёбра DFS-дерева (в «новые» вершины), • обратные рёбра (в пройденные вершины).
- 9. DFS-дерево и обратные рѐбра При поиске в глубину рёбра графа разбиваются на два типа: • рёбра DFS-дерева (в «новые» вершины), • обратные рёбра (в пройденные вершины).
- 10. DFS-дерево и обратные рѐбра При поиске в глубину рёбра графа разбиваются на два типа: • рёбра DFS-дерева (в «новые» вершины), • обратные рёбра (в пройденные вершины).
- 11. DFS-дерево и обратные рѐбра При поиске в глубину рёбра графа разбиваются на два типа: • рёбра DFS-дерева (в «новые» вершины), • обратные рёбра (в пройденные вершины).
- 12. DFS-дерево и обратные рѐбра При поиске в глубину рёбра графа разбиваются на два типа: • рёбра DFS-дерева (в «новые» вершины), • обратные рёбра (в пройденные вершины).
- 13. DFS-дерево и обратные рѐбра При поиске в глубину рёбра графа разбиваются на два типа: • рёбра DFS-дерева (в «новые» вершины), • обратные рёбра (в пройденные вершины).
- 14. DFS-дерево и обратные рѐбра При поиске в глубину рёбра графа разбиваются на два типа: • рёбра DFS-дерева (в «новые» вершины), • обратные рёбра (в пройденные вершины).
- 15. Фундаментальные циклы Каждое обратное ребро вместе с путём по DFS-дереву образует фундаментальный цикл.
- 16. Фундаментальные циклы Каждое обратное ребро вместе с путём по DFS-дереву образует фундаментальный цикл.
- 17. Фундаментальные циклы Любая пара фундаментальных циклов либо не имеют общих рёбер, либо их пересечение — путь в DFS-дереве. (Иначе противоречие с отсутствием циклов в дереве.)
- 18. Фундаментальные циклы Если DFS произвести в плоском графе, то каждый фундаментальный цикл будет сориентирован • по часовой стрелке («вправо»)
- 19. Фундаментальные циклы Если DFS произвести в плоском графе, то каждый фундаментальный цикл будет сориентирован • по часовой стрелке («вправо») • либо против часовой стрелки («влево»)
- 20. Фундаментальные циклы и стороны рѐбер
- 21. Точки возврата и нижние точки
- 22. Точки возврата и нижние точки
- 23. Развилки фундаментальных циклов Развилка двух циклов, пересекающихся по рёбрам, — это тройка рёбер • последнее общее ребро, • и следующие за ним два ребра, относящиеся к различным циклам.
- 24. Фундаментальные циклы в укладке планарного графа • Два цикла, имеющие общие рёбра, ориентированы одинаково т. и т.т., когда один цикл лежит внутри другого.
- 25. Фундаментальные циклы в укладке планарного графа • Два цикла, имеющие общие рёбра, ориентированы одинаково т. и т.т., когда один цикл лежит внутри другого.
- 26. Фундаментальные циклы в укладке планарного графа • Два цикла, имеющие общие рёбра, ориентированы одинаково т. и т.т., когда один цикл лежит внутри другого. • Если циклы вложены друг в друга, то порядок вложения зависит от порядка, в котором на дереве расположены нижние точки обратных рёбер.
- 27. Основное свойство сторон рѐбер в планарном графе
- 28. Основное свойство сторон рѐбер в планарном графе
- 29. ЛП-разбиение
- 30. ЛП-разбиение
- 38. Продолжение ЛП-разбиения на рѐбра дерева
- 39. Продолжение ЛП-разбиения на рѐбра дерева
- 40. Как по ЛП-разбиению строить укладку
- 41. Как по ЛП-разбиению строить укладку
- 42. Как по ЛП-разбиению строить укладку Полный порядок в вершине устроен так: • сначала входящее ребро • затем левые исходящие рёбра, окружённые своими левыми и правыми обратными рёбрами • затем правые исходящие рёбра, окружённые своими левыми и правыми обратными рёбрами
- 43. Конфликт двух правых рѐбер
- 44. Конфликт двух правых рѐбер
- 45. Конфликт двух правых рѐбер
- 46. Конфликт двух правых рѐбер
- 47. Конфликт двух правых рѐбер
- 48. Конфликт двух правых рѐбер
- 49. Конфликт двух правых рѐбер