двох множин, для якої елементи V називають вершинами графа, елементи Е- його ребрами і для кожного ребра еЄЕ вказано дві вершини v1,v2Є V, (можливо v1=v2), які називають кінцями ребра е. для довільного графа G множини його вершин і ребер інколи позначаємо V(G) і Е(G). Надалі розглядаємо тільки скінченні графи (зі скінченною кількістю вершин і ребер). Графи зручно зображати на площині: вершини – точками, а ребра – дугами між ними. Звичайно до графа висувають вимогу, що між кожними двома вершинами повинно бути не більш ніж одне ребро, і один кінець ребра не може збігатись з іншим (немає петель). Якщо у графі дозволено петлі, то його називають псевдо графом. Якщо ребро спрямоване від однієї вершини до іншої, тобто перша з них є початком, а друга кінцем, то таке ребро називають орієнтованим і позначають стрілкою. Граф ребра якого орієнтовані наз. орієнтованим графом або орграфом.
Способи задання графів:
1)геометричний(вершини – точками, а ребра – дугами між ними, або векторами(стрілками) в орграфі);
матричний
а)матрицею суміжності(матриця n розмірності, де n- к-сть вершин,
а елемент (i,j)=1 якщо існує шлях з вершини і в j, інакше (i,j)=0)
б)м-цею інцедентності(n*m, к-сть рядків відповідає к-сті вершин, а стовпців – к-сті ребер;для неорієнтованого графа елемент (i,j)=1 якщо ребро j сполучене з вершиною і , та(i,j)=0 в іншому випадку;для орграфа: елемент (i,j)=1, якщо і є початковою вершиною ребра j ,(i,j)=-1 – і є кінцевою вершиною ребра j та (i,j)=0 – в іншому випадку
Розрізняють повні(К3, к-сть ребер С2n)та неповні графи
Над графами виконують такі дії:
А) з довільного графа G можна вилучити будь-яку вершину v разом з всіма ребрами кінцем яких він є. Отриманий граф познач. G\{v}.
Б)В довільному графі можна ототожнити дві вершини, замінивши їх одною вершиною. При цьому для всіх ребер, кінцем для яких була v1 або v2 кінцем вважатиметься u. При цьому можуть з’явитися петлі і кратні ребра (ребра, які з’єднують ті ж вершини).
В) якщо для довільного ребра е графа G ототожнити його кінці v1 і v2 то цю дію наз. стягуванням даного ребра. При цьому можливо доведеться вилучити отриману петлю, якщо граф не може бути псевдо графом.
Г) довільні графи G1 і G2 можна об’єднати отримавши новий граф G з V(G) = V(G1)UV(G2) Е(G) = Е(G1)UЕ(G2). Якщо Е(G1)?Е(G2) =ш, то це об’єднання наз. диз’юктивним.
Д) для довільних графів G1 і G2 розглядаємо їх добуток G1хG2. Вважаємо, що V(G1хG2) = =V(G1)хV(G2), тобто вершини нового графа – це пари (v1,v2), де v1ЄV(G1), а v2Є V(G2). Стрілки маємо 2-ох сортів: вигляду (е1, v2) та (v1,е2), де е1 – ребро G1, v2 – вершина G2, v1 – вершина G1, а е2 – ребро G2. якщо ребро е1 сполучає вершини z i t, то (е1, v2) сполучає (z,V2) з(t ,V2). Аналогічно з(t , v2). Якщо е2 сполучає а і b, то (v1,а) і (v1,b).
Вершини v1 і v2 називають суміжними, якщо існує ребро з v1в v2. Відповідно для кожного графа G можна скласти матрицю суміжності S(G), у якій S kl=1, якщо існіє ребро з vk у vl.
Якщо граф містить n вершин, то матриця S(G) має розмір nх n.
Ребра еk і еl називаються суміжними, якщо кінець першого з них збігається з початком другого.
Графи Ейлера – неорієнтовані графи, в якихіснує маршрут від довільної вершини до цієї ж вершини, який містить всі ребра цього графа лише 1 раз. Гамільтоновий граф – неор. графи, в якихіснує маршрут від даної вершини до даної, який містить кожну вершину цього графа лише 1 раз.
Для будь-якого графа можна записати список суміжності верши, вказавши для кожної вершини vі довжину Г-(v і).
Для довільної вершини v графа G кількість рабер інцидентних з v називають степенем вершини v і позначають d(v)(degree). Зокрема кожне ребро, яке починається і закінчується в v (петля) рахується двічі.
Якщо d(v)=0, то вершина v наз ізольованою, а при d(v)=1 наз кінцевою або висячою.число d(v) для графа без кратних ребер(мають спільний початок і кінець) збігається з потужністю множтни Г(v ). Якщо всі вершини мають однаковий степінь, то граф G називається регулярним, а число S(G)=?(G)=r(G) називають степенем регулярноті графа.
Теорема Ейлера: сума степенів вершин графа рівна подвоєній кількості його ребер.
Граф називається тривіальним, якщо у ньому немає ребер. Якщо всі вершини графа з’єднані ребрами, то граф називається повним. Граф 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