Елементи теорії графів, Детальна інформація
Елементи теорії графів
Тип документу: Реферат
Сторінок: 3
Предмет: Математика
Автор: Олексій
Розмір: 6.1
Скачувань: 2390
Реферат на тему:
Елементи теорії графів
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. Об'єднання, перетин та композиція (добуток) графів. Відбиття властивостей відношень на графах. Декартовий добуток графів.
Елементи теорії графів
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. Об'єднання, перетин та композиція (добуток) графів. Відбиття властивостей відношень на графах. Декартовий добуток графів.