Ядро диграфа

Ядро диграфа D=(V,E) – множество вершин, которое одновременно является out доминирующим и независимым.

Проблема нахождение ядра диграфа является NP-полной.

.12. Эйлеровы диграфы

Эйлеровым диграфом называется связный диграф, содержащий замкнутую прогулку со всеми дугами диграфа, взятыми точно по одному разу. Эта прогулка называется эйлеровым туром.

Связный диграф будет эйлеровым тогда и только тогда, когда для каждой вершины полустепень исхода равна полустепени захода.

Существует формула определения числа эйлеровых туров в диграфе, названная по начальным буквам фамилий авторов BEST-формулой. Приведем некоторые предварительные определения:

· [A] – матрица связности диграфа;

· [M] = diag(d₁,d₂,d₃,…,d_|V|) – матрица, где диагоналями являются степени исхода (или захода) всех аершин диграфа, а остальные элементы – нули;

· [D] = [M] – [A] – Лапласиан или матрица Кирхгофа диграфа;

· D - детерминант (i,j) алгебраического дополнения матрицы [D] (все (i,j) алгебраические дополнения [D] равны между собой);

Тогда число эйлеровых туров в слабо связанном графе R равно (BEST-формула):

R = (d₁-1)! (d₂-1)!…(d_n-1)!

2.13. Гамильтоновы диграфы

Гамильтоновым называется контур, содержащий все вершины данного диграфа.

Гамильтонов диграф – граф, содержащий гамильтонов контур.

Пусть D будет сильно связным диграфом с n вершинами. Если полустепень исхода deg⁺(v_i) n/2 и полустепень исхода deg ^-(v_i) 2 для каждой вершины v_I, тогда D будет гамильтоновым.

Планарность диграфов

Диграф будет планарным, если его граф основания планарен. Иными словами, планарным диграфом называется диграф, который может быть нарисован на плоскости без пересечения его дуг (точнее, дуги могут пересекаться только на вершинах).

Совершенно очевидно, что свойство планарности диграфов не зависит от направленности дуг, поэтому для диграфов справедливы определения и алгоритмы нахождения планарности их графов основания.