Лабораторна робота №1 Основні поняття теорії графів
Мета роботи: Ознайомлення студентів з основними поняттями теорії графів, поданням графів за допомогою матриці суміжності та матриці інцидентності, локальними ступенями вершин графа, повними графами, ізоморфізмом графів, частинами графа, суграфами та підграфами.
Теоретичні відомості
Нехай V - довільна множина, Е - деяка множина пар виду (vi, vj), де vi, vjV, тобто EV V. Сукупність двох множин G=(V,Е) називається графом з множиною вершин V і множиною ребер E. Графи зручно представляти графічно. При цьому елементи множини V зображають точками на площині, а ребра (vi, vj) відрізками (прямолінійними або криволінійними), що з'єднують точки vi і vj. Граф називається кінцевим, якщо безліч його вершин і ребер кінцева. Множину вершин графа G звичайно означають V(G), а множину ребер - Е(G).
Кількість вершин в графі n(G) називають його порядком. Кількість ребер графа, інцідентних деякій вершині v, називається локальним ступенем або просто ступенем вершини v і означається (v). Якщо е=(v, w)Е(G), то кажуть:
Вершини v і w суміжні;
Вершини v і w є кінцями ребра е;
Вершини v і w інцідентні ребру е;
Ребро е інцідентне вершині v і вершині w.
Два ребра називаються суміжними, якщо обидва вони інцідентні одній вершині.
Якщо пари (v, w)Е вважаються впорядкованими, то граф називається орієнтованим. У другому випадку граф називається неорієнтованим. Ребра орієнтованого графа прийнято називати дугами і зображати направленими відрізками.
Коли граф G - кінцевий, для опису його вершин і ребер досить їх занумерувати. Нехай v1, v2,..., vn - вершини графа G; e1, e2,.., еm - його ребра. Відношення інцідентності можна визначити матрицею ||ij||, що має m рядків і n стовпців. Стовпці відповідають вершинам графа, рядки - ребрам. Якщо ребро ei інцідентно вершині vj, то ij=1, в іншому випадку ij=0. Це так звана матриця інцідентності звичайного графа G, яка є одним з способів його визначення.
Для графів, зображених на малюнках матриця інцідентності має нступний вигляд:
-
v1
v2
v3
v4
v5
v6
v7
v1
v2
v3
v4
v5
v6
v7
e1
1
1
0
0
0
0
0
e1
-1
1
0
0
0
0
0
e2
1
0
1
0
0
0
0
e2
-1
0
1
0
0
0
0
e3
0
1
0
1
0
0
0
e3
0
-1
0
1
0
0
0
e4
1
0
0
0
1
0
0
e4
0
0
-1
0
1
0
0
e5
0
1
0
0
0
1
0
e5
0
0
-1
0
0
1
0
e6
0
0
1
1
0
0
0
e6
0
0
-1
0
0
0
1
e7
0
0
1
0
1
0
0
e7
0
0
0
0
0
0
2
e8
0
0
0
1
0
1
0
e8
0
-1
1
0
0
0
0
e9
0
0
0
0
1
0
1
e10
0
0
0
0
0
1
1
e11
0
0
0
0
1
1
0
Матриця суміжності графа - це квадратна матриця ||ij||, стовпцям і рядкам якої відповідають вершини графа. Для неорієнтованого графа ij дорівнює кількості ребер, інцідентних i-й і j-й вершинам.
Матриці суміжності розглянутих раніше графів мають наступний вигляд:
-
V1
V2
V3
V4
V5
V6
V7
V1
V2
V3
V4
V5
V6
V7
V1
0
1
1
0
1
0
0
V1
0
1
1
0
0
0
0
V2
1
0
0
1
0
1
0
V2
0
0
1
1
0
0
0
V3
1
0
0
1
1
0
0
V3
0
0
0
0
1
1
1
V4
0
1
1
0
0
1
0
V4
0
0
0
0
0
0
0
V5
1
0
1
0
0
1
1
V5
0
0
0
0
0
0
0
V6
0
1
0
1
1
0
1
V6
0
0
0
0
0
0
0
V7
0
0
0
0
1
1
0
V7
0
0
0
0
0
0
1
Граф Н називається частиною графа G(HG), якщо множина його вершин V(Н) міститься в множині V(G), а множина Е(Н) ребер - в Е(G). Якщо V(Н)=V(G), частина графа називається суграфом. Підграфом G(U) графа G називається частина графа з множиною вершин UV, якщо обидва кінці всіх її ребер належать U.
Маршрутом М в графі G називається така кінцева або нескінченна послідовність вершин і ребер, яка чергується (…v1, е1, v2, е2,…, vn-1, еn-1, vn,…), що кожні два сусідні ребра ei-1 і ei мають загальну інцідентну вершину vi. Маршрут М називається ланцюгом, якщо кожне ребро зустрічається в ньому не більше, ніж один раз, і простим ланцюгом, якщо будь-яка вершина, крім, можливо, початкової, зустрічається в ньому не більше, ніж один раз. Маршрут зветься циклічним або замкнутим, якщо він починається і звершується в одній і тій же верхівці. Якщо ланцюг замкнений, то його називають циклом, якщо простий ланцюг замкнений, то його називають простим циклом. Граф, будь-які 2 верхівки якого з’єднані маршрутом, зветься зв’язаним.
Ейлерові графи - це такі графи, в яких існують цикли, що проходять через усі верхівки, тобто які можна зобразити одним розчерком пера, причому процес такого зображення починається і закінчується в одній і тій же точці.
Теорема Ейлера. Кінцевий неорієнтований граф G ейлерів тоді і тільки тоді, коли він зв'язний і ступені всіх його вершин парні.
Гамільтоновим циклом називається простий цикл, що проходить через всі вершини графа, що розглядається. Граф, що містить гамільтонів цикл, називається гамільтоновим.
Дводольний граф Gm, n - це граф, множину вершин якого можна розбити на дві підмножини V1 і V2: , таким чином, що кожне ребро графа з'єднує вершини з різних підмножин.
Граф G називається деревом, якщо він є зв'язним і не має циклів. Наступні твердження еквівалентні:
граф G є дерево;
граф G є зв'язним і не має простих циклів;
граф G є зв'язним, і число його ребер рівно на одиницю менше числа вершин;
будь-які дві різні вершини графа G можна з'єднати єдиним (і притому простим) ланцюгом;
граф G не містить циклів, але, додаючи до нього будь-яке нове ребро, отримуємо рівно один (з точністю до напряму обходу і початкової вершини обходу) і притому простий цикл (що проходить через ребро, що додається ).