Главная > Методы обработки данных > Графы, сети и алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

7.6. Замечания, касающиеся литературы

Для дальнейшего изучения рекомендуются статьи [7.4, 7.11, 7.14] и книги [7.6, 7.13, 7.15, 7.16]. Алгоритм проверки планарности графа можно найти в работе [7.17].

Представляет интерес следующие две характеристики непланарного графа:

1. Минимальное число планарных подграфов, объединение которых дает граф G, называется толщиной графа

2. Минимальное число скрещиваний (или пересечений) ребер в изображении на плоскости графа называется числом скрещиваний графа

Некоторые результаты, касающиеся толщины и числа скрещиваний непланарных графов, можно найти в работах [7.6, 7.18].

<< Предыдущий параграф Следующий параграф >>
Оглавление