).
3) Нехай G - орієнтований мультіграф з непустою безліччю дуг. Тоді:
а) сума рядків матриці I (G) є нульовою рядком;
б) будь-який рядок матриці I (G) є лінійною комбінацією інших рядків;
в) ранг матриці I (G) НЕ перевершує n-1;
г) для будь-якого контуру матриці G сума стовпців матриці I (G), відповідних дуг, що входять у цей контур, дорівнює нульовому стовпцю.
4) Нехай G - мультіграф з непустою безліччю ребер. Тоді при покоординатного складення за модулем 2:
а) сума рядків матриці I (G) є нульовою рядком;
б) будь-який рядок матриці I (G) є сумою інших рядків;
в) для будь-якого циклу в G сума стовпців матриці I (G), відповідних ребрах, що входять у цей цикл, дорівнює нульовому стовпцю.
Щоб підрахувати всі варіанти, які могли б тут виникнути, зауважимо, що можна розглядати чи граф G, або орієнтований граф (орграф) D, в якому розділяються. Мережа N можна визначити як граф або орграф, розглянутий разом з функцією, що приписує кожному ребру деяке позитивне дійсне число. Якщо G - довільний планарний (р, орграф і р ^ З, то а ^ Зр - 6. Орієнтований граф, або орграф, D складається з кінцевого непорожньої множини V вершин і заданого набору X впорядкованих пар різних вершин.
Спрямований граф - це орграф, що не має симетричних пар орієнтованих ребер.
Матриця смежностей поміченого орграфа D визначається аналогічно: Л = Л (D) - | | а ^ - | |, де а ^ = 1, якщо дуга v {V] належить D, і ац = 0 в іншому випадку. З визначення матриці A (D) випливає, що матрицю смежностей даного графа можна також розглядати як матрицю смежностей симметрического орграфа. Якщо D - орграф з лінійними подграфа DI, В»= 1, 2,. Будь-якому графу G поставимо у відповідність орграф D, в якому вершини vt і V) з'єднані дугами vtVj і VjVt тільки в тому випадку, якщо ці вершини суміжні в G. Компоненти лінійного подграфа графа G, які є окремими ребрами, взаємно однозначно відповідають 2-контурам лінійного подграфа орграфа D, а компоненти, що є простими циклами графа G, відповідають двом простим контурам орграфа D.
Далі, кожній дузі орграфа D (F), скажімо йде з вершини fi у вершину fj, приписується колір, пов'язаний з елементом/71// групи F. Щоб побудувати граф G, група (Автоморфізмів) Г (G) якого ізоморфна F, він замінює кожну дугу fifj орграфа D (F). Для р ^ г 4 не існує таких орграфов D, чтого (/}) == А ^. Для орграфов потрібно використовувати редуцированную упорядковану парну групу Sp2. За визначенню група 5р2 діє на безлічі V ^ як індукована групою Sp: кожна підстановка а з Sp індукує таку підстановку а 'з 5р2', що а '(i, /) = (Ai, а /) для (г, /) з 1 ^ 4 Застосовуючи теорему Пойа до циклової індексом групи S [P2 отримуємо многочлен dp (x), в якому коефіцієнт при х9 дорівнює числу орграфов з q орієнтованими ребрами.
Властивості орграфов, які відрізняють їх від графів. Сформулювавши принцип орієнтованої подвійності, ми перейдемо до вивчення матриць, пов'язаних з орграфа, і потім наведемо аналог матричної теореми про дерева у графах.
орграфов і соєдініми
Орграф D складається з кінцевого безлічі V вершин і набору впорядкованих пар різних вершин. У орграфе (орієнтованим) маршрутом називається чергується послідовність вершин і дуг v9, хг, uit. Середні вершини збігаються; основний маршрут містить всі вершини. Оскільки граф може бути або зв'язковим, або ні, то існують три різні способи визначення зв'язності орграфа і кожен з них має свою власну ідіосинкразію). Ясно, що кожен сильний орграф - односторонній, а кожен односторонній орграф - слабкий, але зворотні твердження не вірні.
Орграф називається незв'язним, якщо він навіть не слабкий. Зауважимо, що тривіальний орграф, що складається тільки з однієї вершини, чи є (за визначенням) сильним, оскільки в ньому немає двох різних вершин. Сформулюємо тепер необхідні і достатні умови, що забезпечують орграфов одну з цих трьох типів соєдініми. Орграф місцями тоді і тільки тоді, коли він має остовно замкнутий маршрут; односторонній тоді і тільки тоді, коли він має основний маршрут; слабкий тоді і тільки тоді, коли він має основний полупуть. Для орграфа визначені три типи компонент (зв'язності). Сильної компонентою орграфа називається максимальний сильні л подграф, односторонньої компонентою - максимальний односторонній подграф і слабкою компонентою - максимальний слабкий подграф. Це, зокрема, демонструє спосіб побудови за сильним компонентам орграфа D нового орграфа, який хоча і простіше D, але зберігає деякі його структурні властивості. Конденсацією l) D * орграфа D називається орграф, безліччю вершин якого служить безліч {Si, 52,. , Sn} всіх сильних компонент орграфа D, а дуга йде з St до Sj, якщо в орграфе D є принаймні одна дуга, що йде з деякої вершини компоненти St до вершини компоненти Sj.
Орграф і його конденсація
З максимальності сильн...
