Ребра еk і еl називаються суміжними, якщо кінець першого з них збігається з початком другого. Якщо граф G містить m ребер, то можемо записати матрицю суміжності ребер Sе(G) mхm у якій елемент Sе,kl=1, якщо ребра еk і еl суміжні.

Для довільної вер-ни v графа G позн-ть Г(v ) мн-ну всіх вершин,сполучених дугами з v. Зокрема, Г+(v )- mі вершини, з яких існує ребро у v , Г-(v )- mі, у які існує ребро з v. Для неорієнтованих графів Г+(v)= Г-(v )= Г(v ).

Для будь-якого графа можна записати список суміжності верши, вказавши для кожної вершини vі довжину Г-(v і).

Для довільної вершини v графа G кількість рабер інцидентних з v називають степенем вершини v і позначають d(v)(degree). Зокрема кожне ребро, яке починається і закінчується в v (петля) рахується двічі. Кіькість ребер, які виходять з v називають напівстепенями виходу і позначають d-(v), а ребер, що заходять у v називають напівстепенем заходу і познач d+(v). Очевидно, що d-(v)+ d+(v)= d(v).

Якщо d(v)=0, то вершина v наз ізольованою, а при d(v)=1 наз кінцевою або висячою.число d(v) для графа без кратних ребер(мають спільний початок і кінець) збігається з потужністю мн-ни Г(v ).Аналогічно для графа без кратних ребер d-(v)= |Г-(v )|, d+(v)= |Г+(v )|. Позн-мо S(G)=mind(v) при vЄV(G), ? (G)=maxd(v) при vЄV(G). Якщо S(G)= ? (G) (всі вершини мають однаковий степінь), то граф G наз-ся регулярним, а число S(G)=?(G)=r(G) наз-ть степенем регулярноті графа.

Т Ейлера: сума степенів вер-н графа рівна подвоєній кіл-ті його ребер.

Доведення: якщо перерахувати всі ребра і для кожного з них записати його кінці, то кожна вершина зустрічатиметься стільки разів кінцем скількох ребер вона є. Отже, кількість разів, які згадуються v ,рівна степеню d(v). Всі вершини будуть згадані d(v1)+ d(v2) +d(v3)+…+ d(vn) разів. Але кожне з m ребер додає у список 2 вершини, тому d(v1)+ d(v2)+…+ d(vn)=2 m. Теор доведено.

Граф наз-ся тривіальним, якщо у ньому немає ребер. Якщо всі вершини графа з’єднані ребрами, то граф називається повним. Граф G наз-ся дводольним, якщо його вершини V (G) можна розбити на дві підмн-ни V1 і V2 такі, що: 1) деякі вершини з V1сполучені ребром з деякими верш-ми з V2; 2) не існує ребер ні між верш-ми з V1, ні між вер-ми з V2.

5. Алгоритм Флойда, Алг.Дійкстри

Граф називається зваженим, якщо кожному його ребру співставлено деяке ребро, яке називаємо вагою цього ребра. Довжиною цього маршруту наз. суму ваг всіх ребер, що входять до нього. Тобто вагу інколи розуміють як довжину ребра. В незваженому графі довжини всіх ребер вважаємо рівними 1.В орієнтованому чи неорієнт. графі найкоротші шляхи між всіма парами вершин можна одночасно знайти з допомогою алгоритму Флойда. Для цього для графа з n вершинами утворимо 2 масиви nхn, які можна записати одночасно в одній таблиці |

1 | 2 | … | n

1 | d11

k11 | d12

k12 | d1n

k1n

2 | d21

k21 | d22

k22 | d2n

k2n

…

dn1

kn1 | dn2

kn2 | dnn

knn

В цій таблиці dij – довжина найкоротшого досі знайденого маршруту з вершини vi в вершину vj ,а kij – наступна після vi вершина у цьому маршруті. На початку роботи алгоритму вважаємо d11=d22=d33=…=dnn=0 і для вісх вершин vi ,vj між якими існує ребро вважаємо dij довжиною цього ребра, а kij= vj.

Для всіх інших пар вершин вважаємо dij=? (шляху покищо немає), а kij=0(немає наступної вершини).

На початку в таблиці враховані тільки шлахи рівні 1. На кожному кроці алгор. обходимо по черзі всі вітки з індексами і та j та порівнюємо відстані і та j з сумами di1+d1j, di2+d2j, …, din+dnj, тобто з найкоротшими вже отриманими шляхами з vi у vj через v1, v2 ,…,vn. Якщо найменша з цих сум менша від j то замінюємо dij на цю суму і замість kij пишемо вершину kil, де dil+dlj- найменша. Якщо при обході всієї таблиці зробимо хоча б одну зміну, повторюємо крок знову.

Якщо потрібно знайти найкоротший шлях тільки між двома вершинами u та застосовують алгоритм Дійкстри. Для нього у всіх вершинах графа ставлять позначки двох типів – тимчасові і постійні. Кожна позначка має вигляд (d,k), де d- вершини w, d- найкоротший вже отриманий шлях з u в v, k- вершина яка передує w в цьому шляху. На початку постійну позначку (0;0) ставимо тільки у вершині u. В усіх інших верщинах ставимо тимчасові позначки (?,0). В кожний момент навколо вершини, в якій останньою поставлено постійну позначку, розглядаємо всі сусідні вершини з тимчасовими позначками. Якщо остання постійна позначка – у вершині ,а у суідній з нею вершині vj- тимчасова позначка, то порівнюємо числа і di+lij, де lij- довжина з і в j. Якщо сума виявляється меншою, замінюємо на неї dj ,і kj на в тій вершині, сусідній до i в якій тимчасова позначка dj є найменшою, робимо її постійною. Алгоритм зупиняється коли у вершині v ставимо постійну позначку.

Алгоритм Дійкстри для однієї пари вершин вимагає набагато менше обчислень ніж алгоритм Флойда для всіх пар вершин, але застосовується алг. Дійкстри до всіх пар вершин приблизно в 2 довше ніж алг. Флойда.

6. Алгоритм Форда-Фалкерсона.

Означ.: Потоком в мережі G=(V,E) між вершинами s і t називають такий набір потоків по всіх ребрах графа, що для