ВУЗ:
Составители:
Рубрика:
65
При этом в качестве минимального покрытия строк столбцами мо-
жет выступать любое из рёбер {2, 4}, {3, 6}, {4, 5} и {5, 7}. После удале-
ния, для определённости, ребра {3, 6} получаем планарный граф, плоское
представление которого изображено на рис. 28, б. Соединение, которое
соответствует удалённому ребру {3, 6}, показано штриховой линией и
должно быть реализовано на второй плоскости.
Задачи и упражнения
1. Определите разбиение множества заданных неориентированных
графов на классы гомеоморфных графов:
2. Оцените толщину t
(G) графа G:
3. Выделите все запрещённые фигуры в заданном непланарном
графе G и найдите все рёбра, удаление каждого из которых преобразует
его в планарный граф:
а)
б)
в)
г)
д)
е)
ж)
з
)
и)
а)
б)
в)
Страницы
- « первая
- ‹ предыдущая
- …
- 63
- 64
- 65
- 66
- 67
- …
- следующая ›
- последняя »
