UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75855
останнє поновлення: 2016-12-09
за 7 днів додано 12

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваЕлементи теорії графів (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось2154
Скачало468
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

Елементи теорії графів

 

1. Основні поняття

 

1.1. Вершини і ребра

 

Історично перша робота – Ейлер, розв. задачі про Кенігсбергські мости.

 

Графи там, де є елементи (вершини) та зв'язки між ними (ребра). Приклади

– географічні схеми, комбінаційні схеми з функціональних елементів,

залежність між дисциплінами навчальних планів, бінарні відношення тощо.

 

Множина вершин V і множина ребер E. Пари вершин (упорядковані) і

неупорядковані пари – V(V і [V(V]. Функція f з E у V(V або [V(V]. Якщо F

різнозначна, то маємо граф, якщо нерізнозначна – мультиграф. Петлі – (v,

v) чи [v, v].

 

Інцидентність вершин і ребер (incidence – сфера дії), суміжність

(сусідство) вершин. Степінь вершини. Сума степенів вершин і кількість

ребер.

 

Частини графа, підграфи та суграфи. Доповнення графа.

 

Ізоморфізм графів. Автоморфізми.

 

Дводольний, повний, регулярний, фактор.

 

Паросполучення. Досконале, максимальне.

 

Задачі

 

****Про суму степенів вершин і кількість ребер.

 

ГС1: 1, 3, 4, 25(1, 2)

 

****Про ізоморфізм – на картинках, матрицях суміжності та ін.

 

ГС1: 2, 14(1), 15(1), 16, 18', 28,

 

****Про паросполучення. ГС1: 44

 

1.2. Подання графів і мультиграфів

 

Подання графів (не мультиграфів) – матриця суміжності, список ребер (пар

вершин), структура суміжності – список вершин із списками їх сусідів

("ущільнена" матриця).

 

Подання мультиграфів – матриця інцидентності.

 

Задачі

 

****Малюнки ( матриці, списки, структури тощо.

 

РНД8.8: 24

 

(Липский( Довести, що при будь-якому неорієнтованому графі матриця

суміжності B виражається через матрицю інцидентності A таким чином:

 

B = AAT – diag[d1, d2, …, dn],

 

де AT– це транспонована матриця A, di – степінь i-ї вершини, diag[d1,

d2, …, dn] – діагональна матриця з елементами d1, d2, …, dn на головній

діагоналі.

 

Трох****

 

1.3. Графи та відношення

 

Граф як форма подання відношення на множині V. Об'єднання, перетин та

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

Декартовий добуток графів.

 

Транзитивне, транзитивно-рефлексивне та

транзитивно-рефлексивно-симетричне замикання відношення суміжності.

Зв'язок із матрицею суміжності та її степенями.

 

Задачі

 

****

 

2. Шляхи в графах

 

Шлях, ланцюг, цикл, прості шляхи. Зв'язність. Компонент зв'язності.

Відстані між вершинами. Діаметри, радіуси, центри.

 

Задачі

 

****ГС1: 5, 6, 7, 8, 10, 11, 12, 14(2), 15(2), 25(4, 5), 26, 27, 39(1,

2)

 

РНД8.8: 4,

 

ГС4: 6(1абв), 8(1, 3),

 

Відмітки-відстані на ребрах. Найкоротші шляхи. Алгоритм Дейкстри.

 

****

 

Ейлерові ланцюги та графи. Теорема Ейлера. Гамільтонові цикли та

ланцюги. Задача комівояжера.

 

Задачі

 

****(Ейл.ц.)РНД8.8: 52, на малюнках.

 

****(Гам.ц.)ГС1: 32, 33, 35, 36, 37, 38, 42, 43

 

3. Дерева

 

Дерево, ліс. Код дерева. Охоплююче дерево (каркас, кістяк) мінімальної

ваги. Алгоритми Прима та Краскала.

 

ГС4: 1', 2, 3, 4, 5', 6(2), 7, 8(2), 9, 10, 11, 12, 13(…), 14, 15, 16,

17, 25(1)****про коди: 18(…), 19(…), 20(1, 2), 21(…), 22, 23, 25(2)

 

РНД8.8: 10, 28,

 

****про ОДМВ: ГС4: 27; РНД8.8: 9(аб),

 

4. Планарні графи

 

-----> Page:

0 [1]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ