Основні поняття теорії графів (реферат)

Реферат на тему:

" Основні поняття теорії графів"

Вступ

Роком виникнення теорії графів одностайно вважається рік 1736, коли Леонард Ейлер опублікував розв’язок так званої задачі про кенігсберзькі мости, а також знайшов загальний критерій існування ейлерового циклу в графі.

Отримання дальших суттєвих результатів у цій галузі датують серединою ХIХ століття. Однак початок проведення активних систематичних досліджень та становлення теорії графів як окремішного авторитетного розділу сучасної математики відбулося ще майже 100 років по тому, тобто в середині ХХ століття. Саме з цього часу граф стає однією з найпоширеніших і найпопулярніших математичних моделей у багатьох сферах науки і техніки. Картинка у вигляді набору точок на площині та ліній, проведених між деякими з них, стала зручною і наочною формою зображення найрізноманітніших об'єктів, процесів та явищ.

Великою мірою це пов’язано з виникненням, бурхливим розвитком та поширенням електронних обчислювальних машин і, як наслідок, значним зростанням ролі задач дискретного характеру. Математика від «обслуговування» переважно фізики переходить до проникнення своїх методів у інші сфери людської діяльності. Одним з потужних інструментів такого проникнення є граф.

Із суто формальної точки зору граф можна розглядати як один з різновидів алгебраїчної системи (а саме, як модель), а отже, і всю теорію графів к розділ сучасної алгебри. Справді, результати та методи алгебри широко використовуються в теорії графів. Однак за останні півстоліття активного інтенсивного та екстенсивного розвитку теорія графів виробила свою достатньо специфічну власну проблематику і методологію. На сьогодні теорія графів є однією зі складових математичного апарату кібернетики, важливим розділом дискретної математики.

Поняття графа. Способи завдання графів

Нехай V еяка непорожня скінченна множина, а V (2) ножина всіх двохелементних підмножин (невпорядкованих пар різних елементів) множини V.

Графом (неорієнтованим графом) G називається пара множин (V, E), де E овільна підмножина множини V (2) (E 2)) — позначається G =(V, E).

Елементи множини V називаються вершинами графа G, а елементи множини E ебрами графа G. Відповідно V називається множиною вершин і E ножиною ребер графа G.

Традиційно ребра {v, w} записуються за допомогою круглих дужок (v, w) (іноді просто vw).

Граф, який складається з однієї вершини, називається тривіальним.

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

Нехай задано граф G =(V, E). Якщо (v, w) то кажуть, що вершини v i w є суміжними, у противному разі вершини v i w є несуміжними. Якщо е=(v, w) ебро графа, то вершини v i w називаються кінцями ребра е. У цьому випадку кажуть також, що ребро е з'єднує вершини v i w. Вершина v і ребро е називаються інцидентними, якщо v є кінцем е.

Два ребра називаються суміжними, якщо вони мають спільну вершину.

Існує декілька способів завдання графів.

Одним зі способів завдання графа G =(V, E) є завдання кожної з множин V і E за допомогою переліку їх елементів.

Приклад 3.1. Граф G1=(V1,E1), V1={v1,v2,v3,v4} і E1={(v1,v3), (v1,v4),(v2,v3),(v2,v4),(v3,v4)} е граф із чотирма вершинами і п’ятьма ребрами.

А граф G2=(V2,E2), V2={v1,v2,v3,v4,v5} і E2={(v1,v2),(v2,v4),(v1,v5), (v3,v2),(v3,v5),(v4,v1),(v5,v4)} раф із п’ятьма вершинами і сімома ребрами.

Граф G =(V, E) зручно зображати за допомогою рисунка на площині, який називають діаграмою графа G. Вершинам графа G ставляться у бієктивну відповідність точки площиниточки, що відповідають вершинам v i w, з'єднуються лінією (відрізком або кривою) тоді і тільки тоді, коли v i w суміжні вершини. Зрозуміло, що діаграма графа змінюватиме свій вигляд у залежності від вибору відповідних точок на площині.

Приклад 3.2. На рисунку 3.1 зображені діаграми графів G1 i G2 з попереднього прикладу.

G1 G2.

Рис 3.1.

Графи можна задавати також за допомогою матриць.

Занумеруємо всі вершини графа G натуральними числами від 1 до n. Матрицею суміжності A графа G називається квадратна.

nматриця, в якій елемент aij i-го рядка і j-го стовпчика дорівнює 1, якщо вершини vi та vj з номерами i та j суміжні, і дорівнює 0 у противному разі.

Приклад 3.3. Для графів G1 i G2 маємо відповідно.

A1= $$\begin{array}{c}\text{0011}\\ \text{0011}\\ \text{1101}\\ \text{1110}\\ \\ \mathit{righ}\\ \\ \\ \\ \begin{array}{c}\left(\right)\left(\right)\left(\right)\end{array}\\ \hfill \\ \end{array}$$ i A2= $$\begin{array}{c}\text{1\hspace{0.17em}011}\\ \text{10\hspace{0.17em}110}\\ \text{1\hspace{0.17em}001}\\ \text{11\hspace{0.17em}001}\\ \text{10\hspace{0.17em}110}\\ \\ \mathit{righ}\\ \\ \\ \\ \begin{array}{c}\left(\right)\left(\right)\left(\right)\left(\right)\end{array}\\ \hfill \\ \end{array}$$.

Очевидно, що матриці суміжності графів иметричні.

Занумеруємо всі вершини графа G числами від 1 до n і всі його ребра ислами від 1 до m. Матрицею інцидентності B графа G називається nматриця, в якій елемент bij i-го рядка і j-го стовпчика дорівнює 1, якщо вершина vi з номером i інцидентна ребру ej з номером j, і дорівнює 0 у противному разі.

Приклад 3.4. Для графів G1 і G2 маємо (ребра графів нумеруємо в тому порядку, в якому вони виписані в прикладі 3.1).

B1= $$\begin{array}{c}\text{11\hspace{0.17em}000}\\ \text{110}\\ \text{10\hspace{0.17em}101}\\ \text{1\hspace{0.17em}011}\\ \\ \mathit{righ}\\ \\ \\ \\ \begin{array}{c}\left(\right)\left(\right)\left(\right)\end{array}\\ \hfill \\ \end{array}$$ і B2= $$\begin{array}{c}\text{1\hspace{0.17em}010\hspace{0.17em}010}\\ \text{1\hspace{0.17em}101\hspace{0.17em}000}\\ \text{1\hspace{0.17em}100}\\ \text{100\hspace{0.17em}011}\\ \text{10\hspace{0.17em}101}\\ \\ \mathit{righ}\\ \\ \\ \\ \begin{array}{c}\left(\right)\left(\right)\left(\right)\left(\right)\end{array}\\ \hfill \\ \end{array}$$.

Нарешті, ще одним способом завдання графів є списки суміжності. Кожній вершині графа відповідає свій список. У список, що відповідає вершині v, послідовно записуються всі суміжні їй вершини.

Приклад 3.5. Для графів G1 і G2 маємо списки.

G1: G2:

v1: v3, v4 v1: v2, v4,v5.

v2: v3, v4 v2: v1, v3,v4.

v3: v1, v2,v4 v3: v2, v5.

v4: v1, v2,v3 v4: v1, v2,v5.

v5: v1, v3,v4.

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

2. Підграфи. Ізоморфізм графів. Алгебра графів Граф G1=(V1,E1) називається підграфом графа G =(V, E), якщо V1 E1 /p>

Важливі класи підграфів складають підграфи, які отримуються в результаті застосування до заданого графа операції вилучення вершини і/або операції вилучення ребра.

Операція вилучення вершини v з графа G =(V, E) полягає у вилученні з множини V елемента v, а з множини E сіх ребер, інцидентних v.

Операція вилучення ребра e з графа G =(V, E) е вилучення елемента e з множини E. При цьому всі вершини зберігаються.

Графи G1=(V1,E1) і G2=(V2,E2) називаються ізоморфними, якщо існує таке взаємно однозначне відображення ножини вершин V1 на множину вершин V2, що ребро (v, w) тоді і тільки тоді, коли ребро (),)) Відображення азивається ізоморфним відображенням або ізоморфізмом графа G1 на граф G2.

Таким чином, ізоморфні графи відрізняються фактично лише ідентифікаторами (іменами) своїх вершин. З точки зору теорії графів ця відмінність не є суттєвою, тому звичайно ізоморфні графи ототожнюють і, зображаючи графи у вигляді діаграм, або зовсім не ідентифікують їхні вершини, або нумерують вершини натуральними числами.

Ізоморфне відображення графа G на себе називається автоморфізмом графа G. Автоморфізм рафа G =(V, E), при якому для кожної вершини v виконується)=v, називається тривіальним автоморфізмом.

Приклад 3.6. Пропонуємо переконатись, що всі графи, зображені на рис. 3.2, ізоморфні між собою, а графи на рис. 3.3 е є ізоморфними.

G1 G2 G3.

Рис. 3.2.

H1 H2.

Рис. 3.3.

Відношення ізоморфізму є відношенням еквівалентності на сукупності графів.

Теорема 3.1. Графи G1 та G2 ізоморфні тоді і тільки тоді, коли матрицю суміжності (матрицю інцидентності) одного з цих графів можна одержати з матриці суміжності (матриці інцидентності) іншого графа за допомогою відповідних перестановок рядків та стовпчиків.

Доведення. Справді, як було зазначено вище, ізоморфні графи G1 і G2 відрізняються між собою лише порядком нумерації вершин, тобто існує бієктивне відображення ножини номерів вершин першого графа на множину номерів вершин другого. Отже, кожен елемент aij (1) матриці суміжності A1 графа G1 збігається з елементом a (2) (тобто елементом, який знаходиться в рядку з номером) і стовпчику з номером)) матриці суміжності A2 графа G2. Таким чином, шляхом послідовного одночасного обміну місцями (перестановок) рядків і стовпчиків з номерами i та) для всіх i=1,2,…, n матрицю суміжності A1 можна перетворити у матрицю суміжності A2 і навпаки.

Якщо відображення ідоме, то таке перетворення виконати неважко. У разі ж, коли потрібно перевірити за допомогою матриць суміжності, чи є ізоморфними два задані графи з n вершинами кожний, необхідно здійснити різноманітні одночасні перестановки рядків і стовпчиків однієї з них. Якщо після чергової з таких перестановок дістанемо матрицю, яка повністю збігається з іншою, то ці графи ізоморфні. Однак, щоб в такий спосіб з’ясувати, що задані графи не є ізоморфними, потрібно виконати всі n! перестановок рядків і стовпчиків. Вже для порівняно невеликих значень n здійснити цей перебір практично неможливо навіть за допомогою обчислювальної машини. У прикладній теорії алгоритмів розробляються різноманітні алгоритми перевірки ізоморфізму графів, які для більшості графів (або окремих типів графів) дозволяють суттєво скоротити обсяг необхідних перевірок [2,7,8].

Для матриць інцидентності графів G1 і G2 з n вершинами і m ребрами кожний справедливі аналогічні міркування. Відмінність у тому, що коли G1 і G2 ізоморфні, тоді для їхніх множин вершин існує бієкція, а для множин ребер нша бієкція Загальна ж кількість необхідних кроків для перевірки ізоморфізму графів G1 і G2 у цьому випадку не перевищує n! m!

Граф G =(V, E) називається повним, якщо будь-які дві його вершини суміжні (тобто E=V (2)). Повний граф з n вершинами позначається Kn.

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

Для графів можна означити операції об'єднання, перетину і доповнення.

Об'єднанням графів G1=(V1,E1) і G2=(V2,E2) називається граф G =(V1E1- позначається G =G1 Об'єднання G =G1називається прямою сумою графів G1 i G2, якщо V1p>

Перетином і різницею графів G1=(V, E1) i G2=(V, E2) з однаковими множинами вершин називаються графи ­­G, E1 i G =(V, E1E2) відповіднопозначаються ­­G і ­­G = G1G2.

Доповненням графа G =(V, E) називається граф $$\stackrel{}{G}$$ =(V, V (2)E). Отже, граф $$\stackrel{}{G}$$ має ту саму множину вершин V, що і граф G, а вершини графа $$\stackrel{}{G}$$ уміжні тоді і лише тоді, коли вони несуміжні в G. Для графа G з n вершинами виконується $$\stackrel{}{G}$$ =KnG.

Таким чином можна означити алгебру графів A=<Г,{}> (типу (2,2,1)), носієм якої є множина Г всіх графів. Iснують й інші операції для графів, отже, сигнатуру алгебри A можна розширювати.

Неважко переконатись у справедливості такого твердження.

Теорема 3.2. Графи G1 i G2 ізоморфні тоді і тільки тоді, коли ізоморфні їхні доповнення $$\stackrel{}{G}$$ 1 i $$\stackrel{}{G}$$ 2.

Приклад 3.7. Об'єднання і перетин графів H1 і H2 з попереднього прикладу зображені на рис. 3.4. Доповнення графів G2 i H2 зображені на рис. 3.5.

H1 H1.

Рис. 3.4.

$$\stackrel{}{G}$$ 2 $$\stackrel{}{H}$$ 2.

Рис. 3.5.

Граф як модель. Застосування теорії графів

Останнім часом графи і пов’язані з ними методи досліджень використовуються практично в усіх розділах сучасної математики і, зокрема, дискретної математики.

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

Наприклад, у вигляді графа можуть бути зображені:

лектричні і транспортні мережі;

нформаційні і комп’ютерні мережі;

арти автомобільних, залізничних і повітряних шляхів, газоі нафтопроводів;

оделі кристалів;

труктури молекул хімічних речовин;

оделі ігор;

ізні математичні об'єкти (відношення, частково впорядковані множини, решітки, автомати, ланцюги Маркова, алгоритми і програми тощо);

абіринти;

лани діяльності або плани виконання певних робіт (розклади);

енеалогічні дерева тощо.

Приклади застосування теорії графів:

ошук зв’язних компонентів у комунікаційних мережах;

ошук найкоротших, «найдешевших» та «найдорожчих» шляхів у комунікаційних мережах;

обудова кістякового дерева: зв’язність з найменшою можливою кількістю ребер;

ошук максимальної течії для транспортної мережі, в якій визначено вхідні та вихідні вершини та пропускні спроможності ребер;

зоморфізм графів: ідентичність структур молекул (ізометрія);

находження циклів графів:

амільтонів цикл: обійти всі вершини графа, побувавши в кожній з них лише один раз (задача комівояжера);

йлерів цикл: обійти всі ребра (контроль дієздатності мережі);

озфарбування графів: розфарбування географічних карт, укладання розкладів, розміщення ресурсів тощо;

ланарність графів: проектування друкованих електронних та електричних схем, транспортних розв’язок тощо;

находження центрів графа: вершин, максимальна відстань від яких до всіх інших вершин графа є мінімальною («столиць»).

тощо.

Список використаної літератури.

1. 1.Харари Т. Теория графов.- М., 1973.

2. 2.Лекции по теории графов / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р.И.- М., 1990.

3. 3.Зыков А. А. Основы теории графов.- М., 1987.

4. 4.Оре О. Теория графов.- М., 1980.

5. 5.Свами М., Тхуласираман К. Графы, сети, алгоритмы.- М., 1984.

6. 6.Уилсон Р.

   Введение

   в теорию графов.- М., 1977.

7. 7.Кристофидес Н. Теория графов. Алгоритмический подход.- М., 1978.

8. 8.Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. — М., 1980.