2.13. Гамильтоновы диграфы
Гамильтоновым называется контур, содержащий все вершины данного диграфа.
Гамильтонов диграф– граф, содержащий гамильтонов контур.
Пусть Dбудет сильно
связным диграфом сnвершинами. Если полустепень исходаdeg+(vi)
n/2
и полустепень исходаdeg-(vi)
2
для каждой вершиныvI,
тогдаDбудет гамильтоновым.
2.13. Планарность диграфов
Диграф будет планарным, если его граф основания планарен. Иными словами,планарным диграфом называется диграф, который может быть нарисован на плоскости без пересечения его дуг (точнее, дуги могут пересекаться только на вершинах).
Замечание
Совершенно очевидно, что свойство планарности диграфов не зависит от направленности дуг, поэтому для диграфов справедливы определения и алгоритмы нахождения планарности их графов основания.
2.14. Раскраска диграфов
Раскраска вершин ориентированного графа
Определения
Ориентацией простого графа Н является диграф, полученный из Н заменой каждого ребра дугой любой ориентации. Диграф G будет ориентированным графом, если он является ориентацией какого-либо графа Н.
Ориентированной k-раскраскойориентированного графаGявляется разбиениеV(G) наkклассов раскраски, таких, что:
нет двух смежных вершин, принадлежащих к одному и тому же классу раскраски;
в
Меры
се дуги, соединяющие два класса раскраски, имеют одну и ту же направленность.
Ориентированное хромаическое число ocn(G) ориентированного графаG– наименьшее числоk, при которомGимеет ориентированнуюk-раскраску.
Пример
Класс сложности
Задачи k-ориентированной раскраски ориентированного графа и нахожденияocn(G) являютсяNP-тяжелыми.