- •Практическое занятие 1. Способы задания графов. Части и подграфы графов.
- •Практическое занятие 2. Операции над графами.
- •Практическое занятие 3. Бинарные операции над графами.
- •Практическое занятие 4. Маршруты графа. Связные графы.
- •Практическое занятие 5. Метрические характеристики связных графов.
- •Практическое занятие 6. Нод и нок целых чисел. Алгоритм Евклида. Линейное представление нод.
- •Практическое занятие 7. Числовые функции.
- •Практическое занятие 8. Позиционные непозиционные системы счисления. Действия над числами в g-ичной системе счисления.
- •Практическое занятие 9. Алфавитное, префиксное кодирование. Взаимно однозначное кодирование.
- •Практическое занятие 10. Оптимальное кодирование. Алгоритмы Хаффмена и Фано.
- •Практическое занятие 11. Самокорректирующиеся коды. Алгоритм Хэмминга.
- •Практическое занятие 12. Рубежная аттестация №1. Вариант 0
- •: ,,,,,,.
Практическое занятие 1. Способы задания графов. Части и подграфы графов.
Контрольные вопросы:
Мультиграф.
Ориентированное ребро.
Кратные ребра.
Граф.
Ориентированный мультиграф.
Ориентированный граф.
Петля.
Псевдограф.
Смежные вершины.
Смежные ребра.
Степень вершины.
Конечный граф.
Матрица смежности графа.
Матрица инцидентности мультиграфа.
Часть графа.
Подграф графа.
План занятия.
Теоретический диктант.
Решение типовых задач.
Номер задания |
Аудиторная работа |
Домашняя работа |
1 |
1) |
2) |
2 |
1) |
2) |
3 |
1) |
2) |
4 |
1) |
2) |
5 |
1) |
2) |
Задание 1.ГрафGзадан графически. Задать графG
а) аналитически;
б) с помощью матрицы смежности;
в) с помощью списка дуг;
г) с помощью структуры смежности.
1) G: 2)G:
Задание 2.Для графаиз задания 1 выписать и изобразить одну часть и один подграф.
Задание 3.Изобразить графически следующие графы:
а)граф, заданный матрицей смежности:
1)2)
б)граф 6 порядка, заданный списком дуг:
1) 2)
в)граф, заданный с помощью структуры смежности
1) a - a, d 2) a - b, e
b - b, c, d b - a, c
c - a c - c, b
d - - d - d
e - e, a
Задание 4.Составить матрицу инцидентности следующих мультиграфов:
1) G: 2)G:
Задание 5.Изобразить графически мультиграфы, заданные матрицей инцидентности:
1)2)
Практическое занятие 2. Операции над графами.
Контрольные вопросы:
Операция удаления ребра.
Операция добавления ребра.
Операция удаления вершины.
Операция добавления вершины.
Операция введения вершины в ребро (операция подразделения ребра).
Операция отождествления вершин (операция стягивания ребра).
Операция расщепления вершины.
Дополнение графа.
План занятия.
Теоретический диктант.
Проверка домашнего задания.
Решение типовых задач.
Номер задания |
Аудиторная работа |
Домашняя работа |
1 |
а),б) |
в) |
Задание 1.Выполнить следующие операции над графомG:
a)G: б)G: в)G:
1) Удалить ребро (2,3);
2) Добавить ребро (1,5);
3) Удалить вершину 3;
4) Добавить вершину 7;
5) Ввести вершину 5 в ребро(4,1);
6) Отождествить вершины 2и3;
7) Расщепить вершину 3 по разбиениюмножества,;
8) Построить дополнение
Практическое занятие 3. Бинарные операции над графами.
Контрольные вопросы:
Пересечение графов.
Объединение графов.
Кольцевая сумма графов.
Соединение графов.
Произведение графов.
Композиция графов.
План занятия.
Теоретический диктант.
Проверка домашнего задания.
Решение типовых задач.
Номер задания |
Аудиторная работа |
Домашняя работа |
1 |
а) |
б) |
Задание 1.Для графовинайти графы(Записать аналитически и изобразить графически).
а)
G1: G2:
б) G1: G2: