ченого орграфа D алгебраїчне доповнення будь-якого елемента j-го стовпця матриці Mid одно числу остовних виходять дерев, у яких вершина Vj є джерелом. Ейлеров контур у орграфе D - це замкнутий остовно маршрут, в якому кожна дуга орграфа D зустрічається по одному разу. Орграф називається ейлеровим, якщо в ньому є Ейлером контур. Для графів, можна легко показати, що слабкий орграф D Ейлером тоді і тільки тоді, коли у кожної його вершини полустепені заходу дорівнює полустепені результату. Сформулюємо тепер теорему, в якій дається формула для числа ейлерових контурів у ейлерових орграфа. Цю теорему можна довести дуже витончено за допомогою матричної теореми про дерева для орграфов; У ейлерова орграфе число ейлерових контурів одно з (d, - 1)! Зауважимо, що для ейлерова орграфа моа = М А і всі суми і по рядках, і по стовпцях дорівнюють нулю, так що все алгебраїчні доповнення рівні між собою. Перший орграф з трьома вершинами називається транзитивної трійкою, другий - циклічної трійкою. p> Орграф називається строго слабким, якщо він слабкий і не односторонній; строго одностороннім, якщо він односторонній і не сильний. Нехай С0-клас всіх незв'язних орграфов, GI-клас всіх строго слабких орграфов, С2-клас всіх суворо односторонніх орграфов і Ся- клас всіх сильних орграфов. Тоді максимум і мінімум числа q дуг серед всіх орграфов з р вершинами, що відносяться по соєдініми до категорії С;, i = 0, 1, 2, 3,. Орграф, який є декартовим твором DjXZ ^ двох орграфов, має VjX У2 в якості множини вершин, і вершина (В«j, и2) суміжно до вершини (уь у2) тоді і тільки тоді, коли або [ui = 0i і u, adj гл2], або u. Якщо орграф D щодо соєдініми знаходиться в категорії С ", то будемо писати c (D) = n. Ні один суворо слабкий орграф не містить вершину, видалення якої призводить до сильному орграфа.
Реберний орграф L (D) має безліч всіх дуг даного орграфа D в якості множини вершин, і дві його вершини х і у суміжні тоді і тільки тоді, коли дуги х к у породжують маршрут в орграфе D. Висловити число вершин і число дуг орграфа L (D) через відповідні величини орграфа D. Реберний орграф L (D) слабкого орграфа D ізоморфний самому орграфа D тоді і тільки тоді, коли D або D '- функціональний орграф. Якщо D - незв'язних орграф, те твердження, що міститься в попередній вправі, не вірно. Нехай S і Т - непересічні безлічі вершин орграфа D, а X (S, Т) - безліч всіх дуг, що йдуть з S в Т. Орграф D реберний тоді і тільки тоді, коли не існує множин 5 і Т, що мають по дві вершини і таких, що Х (S, T) | = 3. Число ейлерових шляхів орграфа D одно числу гамільтонових контурів реберного орграфа L (D]. Нехай орграф 7 складається з однієї вершини з двома орієнтованими петлями. Нехай T2 = L (T1) - реберний орграф (тут, якщо бути більш точним, потрібно використовувати термін В«ПсевдоорграфВ») орграфа Тг, певний природним чином; рекурсивно визначається Tn = L (Tn, l). (Такі орграфов Т "відомі під назвоюВ« телетайпних діаграм В».) Тоді число ейлерових шляхів у орграфе Т" дорівнює 22 "" 1-1. Кожен орграф, у якого id (v) ^ p/2, od (v) ^ p/2 для будь-якої вершини v, гамільтонів. p> Розглянемо орграфа, у яких для будь-якої вершини і сума ^ d (u, v) відстаней від цієї вершини до всіх інших постійна. Знайти серед цих орграфов орграф, який не є вершинно-симметрическим. Орграф D, його доповнення D і зворотний до нього D 'мають одну і ту ж групу (автоморфізмів). Нехай А-матриця смежностей реберного орграфа повного симметрического орграфа. p> Два орграфа називаються коспектральнимі, якщо їх матриці смежностей мають один і той же характеристичний многочлен. Існують в точності три різних коспектральних сильних орграфа з чотирма вершинами.
Орграф, званий кон'юнкція D = Dl/ D2 двох орграфов Z) j і D2, має в якості множини вершин K = V1XV2, і вершина u = (u1, и2) суміжно до вершини v = (vL, v2) тоді і тільки тоді, коли% adj г, ^ в орграфе Dl і и2 adj v.
Матриця смежностей А кон'юнкції D = Dl/ D2 есть тензорне добуток матриць смежностей орграфов D1 і D2. Нехай Dl і D2-два орграфа, ad, - найбільший спільний дільник довжин всіх простих контурів орграфа D, -, t = l, 2. Кон'юнкція Dlf D ^ є сильним орграфом тоді і тільки тоді, коли Ог і D2 - сильні орграфа, a d1 і d2 взаємно прості.
Орграф називається примітивним, якщо яка-небудь ступінь його матриці смежностей цілком складається з позитивних чисел. Орграф примітивний тоді і тільки тоді, коли довжини його простих контурів мають найбільший спільний дільник, рівний 1. Нехай D - примітивний орграф. Аналогічно для вершин і і v орграфа з і в v. Виняток складають (3,3)-орграф і (4,6)-орграф. П2, складеної Обершельпом, наведені числа орграфов з р вершинами, Ці числа обчислені за допомогою співвідношення (15. L (D) реберний орграф орграфа D.
ОРІЄНТОВАНИЙ ГРАФ (Орграф) G є пара G = (V, E), де V - к-нечное безліч вершин, а E - п-оізвольное підмножина V * V - безліч орієнтованих (спрямованих) ребер (дуг). Пропозиції. p> а) Орієнто...
