26. Деякі спец. Класи простих графів

Повний граф з n вершинами назив граф у якому будь-яку пару вершин з’єднану точно одним ребром.

Граф назив порожнім якщо він не містить ребер.

Граф G(V,E)назив дводольним якщо множину вершин V можна розбити на дві підмножини V1 i V2 так щоб V1(обєднання)V2=V, а V1(переріз)V2=порожній множині

Дводольний граф назив. Повним якщо кожну вершину з V1 зєднано з кожною вершиною V2

Циклом Cn(n>=3) назив. Граф, в якому всі вершини посл1довно з’єднано

Колесом Wn назив граф який можна одержати з циклу Cn додаванням нової вершини з’єднаної з кожною вершиною графа Cn

27. Спосіб подання графів

Найвживаніший спосіб подання графів – це рисунок на площині у вигляді точок і ліній, які з'єднують ці точки. Проте цей спосіб подання абсолютно непридатний, якщо потрібно розв'язувати комп'ютері задачі з графами.

Є декілька інших способів подання графів для двох найважливіших типів графів: простого та орієнтованого – це матриця інцидентності, та матриця суміжності.

Матриця назив. булевою якщо вона склад. з 0 та1.

Матриця інцидентності для неорієнтованого графа називається булеву m*n матрицю з елементами mij якщо вершина Vi кінець ребра Ej, а 0 в іншому випадку. Для простого графа в матриці інцид. в кожному стовпці точно дві одиниці і немає однакових стопців. Для мультиграфа в матриці інцидент. з‘являються однакові стовпці. Для псевдографа якщо у вершині є петля, то на відповідному місці ставимо двійку. Матрицю інцидентності можна також використ для подання оргграфа. Матрицею інцидентн. для оргграфа назив. матриця розм n*m з елементами

mij= | 1, Ej виходить Vi

| -1, Ej входить Vi

| 2, Ej петля Vi

| 0, в інших випадках

-------------------------------------------------------------

Матриця суміжності графа G з n вершинами назив. булеву n*n з елементами

mij= | 1, якщо вершина Vi і верш Vj Є Е

| 0, в іншому випадку

Для неорієнтованого графа aij = aji для простого графа aii=0

Для псевдографа якщо маємо кратні ребра то елемент aij дорівнює кількості ребер що з‘єдн. вершини Vi та Vj а для петлі елемент a22=1

Для орієнтованого графа склад з елементів

mij=1 коли вершини з`єд.

mij=0 в іншому випадку

Для орграфа матриця суміжності не існує.

28. Шляхи та цикли. Звязність

Шляхом довжиною R із вершиною U у вершині V в неорієнтованому графі називають послідовність ребер.

Шлях довжиною r має r ребер. Вершини U та V називають крайніми, а вершини V1, V2, …, Vr-1 називають внутрішніми.

Циклом в неорієнтованому графі називають шлях U=V.

Шлях або цикл називають простим, якщо він не містить повторюваних ребер.

Неорієнтований граф називають зв’язним, якщо будь-які 2 його вершини з’єднані шляхом. В іншому випадку граф називають незв’язним. Незв’язний граф складається з 2 і більше підграфів, кожна пара з яких не має спільних вершин, а ці підграфи називають компонентами зв’язності.

Віддаллю називається довжина найкоротшого шляху між вершинами U та V, а сам шлях називають геодезичним.

Орграф називають сильнозв’язним, якщо для будь-яких його різних вершин U та V існують орієнтовані шляхи від U до V і від V до U.

Орграф називають слабкозв’язним, якщо існує шлях між будь-якими двома його вершинами у відповідному неорієнтованому графі.

Числом реберної зв’язності називають найменшу к-сть ребер, вилучення яких дає незв’язний граф.

Вершину U простого графа G називають точкою з’єднання, якщо граф G у разі її вилучення матиме більший компонент ніж початковий граф G. Ребро називається мостом, якщо його вилучення збільшує кількість компонентів.

Теорема 1: між кожною парою різних вершин зв’язного неорієнтованого графа існує простий шлях.

Теорема 2: якщо простий граф G має n вершин та k-компонент, то кількість m його ребер задовольняє нерівності.

Теорема Кеніга: для того щоб граф був дводольним необхідно і достатньо щоб він не містив простих циклів із непарною довжиною.

29. Ізоморфізм. Два графи називаються ізоморфними, якщо існує перестановка вершин, при якій вони збігаються. Іншими словами, два графи називаються ізоморфними, якщо існує взаємооднозначна відповідність між їх вершинами і ребрами, така що зберігається суміжність та інцидентність.

Ізоморфізм графів Відображення A→B називають бієкцією, якщо це є взаємнооднозначним відображенням множини А в множину В, тобто кожному елементу множини А відповідає єдиний елемент множини В.

Нехай задано графи G1=(V1, E1), G2=(V2, E2). Якщо V1→ V2 бієкція, тобто якщо вершини U та V графа G1 суміжні, то їх образи λ(U) та λ(V) суміжні в графі G2, то відображення λ називають ізоморфізмом, а графи G1 та G2 називають ізоморфними.

Теорема 1: прості графи ізоморфні тоді, і лише тоді, коли їх матриці суміжності можна отримати одна з одної перестановкою рядків та стовпців.