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-тяжелыми.