Лекций – 4 часа
Практик – 6 часов
Контрольная работа – 1 шт. сдать до 11 числа. 11.01.07 – зачет к/р.
Отчетность – зачет.
Литература – T:\Предметы\Дискретка\GED\dm3.doc
Методическое пособие «Дискретная математика»
Варианты заданий на к/р. (1 теор., 4 практ.):
T:\Предметы\Дискретка\GED\semestr5\Варианты заданий.doc
Задания:
T:\Предметы\Дискретка\GED\dm3.doc
T:\Предметы\Дискретка\GED\Экзаменационные задания.doc
Лекция
-
Понятие графа, об чем речь.
-
Рисунок 1:
-
вершины, ребра, мощность, обозначение;
-
смешанный, ориентированный, неориентированный;
-
мультиграф, мультиграфическое число
-
инцидентность, смежность
-
-
Двойственный граф (определение записать), пример рисунок 7
-
Нуль-граф, полный граф (пример Рисунок 8а,б)
-
Локальная степень вершины, висячая вершина, четная, нечетная (на предыдущих примерах), регулярный граф.
-
Подграф, суграф – определение, пример.
-
Объединение, пересечение графов – определение, пример.
-
*Связность графов:
-
Маршрут, длина маршрута, цепь, простая цепь, цикл,
-
Нахождение маршрутов длины q по матрице R.
-
связные вершины, связность графа, компонента связности, степень связности (пример), разделяющее подмножество (мост) пример.
-
-
*Нахождение простых цепей.
-
*Эйлеровы и гамильтоновы графы
-
Эйлеров, полуэйлеров граф – определение, условие существования.
-
Гамильтонов граф – определение.
-
-
Деревья
-
Определение (связный граф без циклов), обозначение T: |X|=n, |U|=n-1
-
Цикломатическое число: понятие, формула, назначение.
-
Покрывающее дерево – определение, пример
-
Назначение покрывающего дерева – построение деревьев минимальной стоимости (пример локальной сети). Метод Краскала.
-
-
*Метрика графа
-
Аксиомы Фреше
-
Матрица расстояний
-
Координатная решетка – рисунок 25.
-
Шаг решетки
-
Размер решетки
-
Расстояние между вершинами в решетке
-
Матрица геометрии
-
-
-
Раскраска графа:
-
Понятие, определение. Внутренняя устойчивость.
-
Хроматическое число
-
Пример раскраски графа
-
Графы Кёнига (двудольные, бихроматические). Пример
-
-
Изоморфизм графов:
-
Понятие, примеры
-
Понятие плоского и планарного графа, примеры.
-
Грань, формула для плоского графа.
-
-
*Орграфы
-
Понятие, матрицы смежности и инциденций
-
Маршрут, путь, контур.
-
Практика
-
Рисунок 5:
-
Матрица смежности, инцидентности, список смежности
-
-
Построить граф по матрице смежности, инцидентности, списку пар
-
Построить объединение, пересечение графов, двойственный граф.
-
Покрывающее дерево
-
Изоморфизм графов.
Задания на контрольную работу «Графы»
№ варианта |
Экзаменационные задания.doc |
№ задачи (dm3.doc к/р№3: стр.154-163 или методичка стр. 160-169) |
|
Теоретическое задание |
Практические задания |
||
|
|
1, 11 |
|
|
|
2, 12 |
|
|
|
3, 13 |
|
|
|
4, 14 |
|
|
|
5, 15 |
|
|
|
6, 16 |
|
|
|
7, 17 |
|
|
|
8, 18 |
|
|
|
9, 19 |
|
|
|
10, 20 |
|
|
|
1, 21 |
|
|
|
2, 22 |
|
|
|
3, 23 |
|
|
|
4, 11 |
|
|
|
5, 12 |
|
|
1 |
6, 13 |
|
|
2 |
7, 14 |
|
|
3 |
8, 15 |
|
|
4 |
9, 16 |
|
|
5 |
10, 17 |
|
|
6 |
1, 18 |
|
|
7 |
2, 19 |
|