епустою множиною дуг. Тоді: а) сума рядків матриці I (G) є нульовою рядком; б) будь-який рядок матриці I (G) є лінійною комбінацією інших рядків; в) ранг матриці I (G) не перевищує n - 1; г) для будь-якого контуру матриці Gсумма стовпців матриці I (G), соответст-чих дугам, що входять до цей контур, дорівнює нульовому стовпцю.
4) Нехай G- мультіграф з непустою множиною ребер. Тоді при покоордінат-ном складення по модулю 2: а) сума рядків матриці I (G) є нульовою рядком; б) будь-який рядок матриці I (G) є сумою інших рядків; в) для будь-якого циклу в Gсумма стовпців матриці I (G), відповідних реб-рам, що входять до цей цикл, дорівнює нульовому стовпцю.
. Операції над графами
Граф H називається подграфом графа G, якщо VH VG, EH EG. Якщо H - під-граф графа G, то кажуть, що H міститься в G. Подграф називається власним, якщо він відмінний від самого графа.
Подграф H називається остовне подграфом графа G, якщо VH=VG.
Якщо безліч вершин подграфа H є U, а безліч його ребер збігається з безліччю всіх ребер графа G, обидва кінці яких належать U, то H називається подграфом, породженим безліччю вершин U, і позначається G (U).
Якщо безліч ребер подграфа H є E EG, а безліч його вершин збігається з безліччю всіх кінців ребер з E вершин графа G, то підграф H називається подграфом, породженим безліччю ребер E і позначається G (E ).
Нехай v - вершина графа G. Тоді операцію побудови графа H=Gv називають видаленням вершини v. Побудований в результаті цієї операції граф H містить всі ребра безлічі ЕG крім інцидентних вершині v, а VH=VG {v}.
Нехай e - ребро графа G. Тоді операцію побудови графа H=Ge називають видаленням ребра e. Побудований в результаті цієї операції граф H містить всі вершини графа G, а EH=EG {e}.
Видалення вершини або ребра, а також перехід до Подграфом - це операції, за допомогою яких можна з наявного графа отримувати інші графи з мен-шим числом елементів.
Розглянемо тепер операції, що дозволяють отримувати з наявних графів графи з великим числом елементів.
Якщо вершини u і v графа G=(VG, EG) не суміжні, то кажуть, що граф H=(VH, EH) отриманий з графа G додаванням ребра e={u, v}, якщо VH=VG і EH=EG {e}, то пишуть H=G + e.
Граф H називається об'єднанням (або накладенням) графів F і G, якщо H=VF? VG і EH=EF? EG. У цій ситуації пишуть H=F? G. Об'єднання F? G називається диз'юнктивним, якщо VF? V G =?. Аналогічно визначаються об'єднання і диз'юнктивне об'єднання будь-якого безлічі графів, причому в останньому випадку ніякі дві з поєднуваних графів не повинні мати спільних вершин.
Нехай G1=(V1, E1) і G2=(V2, E2). Тоді твором графів (позначається G 1? G2) називається такий граф G, для якого VG=V 1? V2- декартово произведе-ня множин вершин вихідних графів, а EG визначається наступним чином: вершини (u1, u2) і (v1, v2) суміжні в графі G тоді і тільки тоді, коли u1=v1, а u2 і v2 суміжні в G2 , або u2=v2, а u1 і v1 суміжні в G1
4. Маршрути, ланцюги, цикли
Переміжна послідовність v1, e1, v2, e2, ..., en, vn + 1 вершин і ребер графа така, що ei=vivi + 1 (i=1, n), називається маршрутом, з'єднує вершини 1 і vn + 1 (або (v1vn + 1) -Маршрут). Очевидно, що для завдання маршруту в графі досить задати послідовність v1, v2, ..., vn + 1. його вершин, або послідовність e1, e2, ..., en його ребер.
Вершина v називається досяжною з вершини u, якщо існує (u, v) -Маршрут. Будь-яка вершина вважається досяжною з себе самої.
Маршрут називається ланцюгом, якщо всі його ребра різні, і простий ланцюгом, якщо всі його вершини, крім, можливо, крайніх, різні. Маршрут (1) називається циклічним, якщо v1=vn + 1. Циклічна ланцюг називається циклом, а циклічна проста ланцюг - простим циклом. Число ребер в маршруті називається його довжиною. Цикл довжини 3 часто називають трикутником. Довжина всякого циклу не менше трьох, якщо мова йде про просте графі, оскільки в такому графі немає петель і кратних ребер. Мінімальна з довжин циклів графа називається його обхватом.
Властивості маршрутів, ланцюгів і циклів:
) Всякий незамкнутий (u, v) -Маршрут, містить у собі просту (u, v) -ланцюг. Зокрема, будь-яка (u, v) -ланцюг, містить у собі просту (u, v) -ланцюг. Причому, якщо (u, v) -Маршрут містить в собі вершину w (w? U і w? V), то в загальному випадку, проста (u, v) -ланцюг може не містити в собі вершину w.
) Всякий непростий цикл можна розбити на два або більше простих. Причому для замкнутого маршруту таке твердження не вірно.
) Всяка непроста (u, v) -ланц...
