Добрый день, уважаемые читатели блога!
Эта статья предназначена для студентов специальности 5.05010201 «Обслуживание компьютерных систем и сетей», изучающих дисциплину «Дискретная математика».
Инструкционная карта №2 для выполнения практической работы по дисциплине «Дискретная математика»:
Контрольные вопросы выбираются в соответствии с номером студента по списку, таким образом: студент с номером по списку 1 отвечает на вопросы №1 и №5, с номером по списку 2 — отвечает на вопросы №2 и №6 и т.д.
Инструкционная карта 2.
на выполнение практического занятия по дисциплине « Дискретная математика»
для студентов специальности 5.05010201”Обслуживание компьютерных систем и сетей”
Тема: Применение теории графов для решения задач.
Цель: Научиться строить различные виды представления графа, решать задачи с использование теории графов.
Норма времени: 2 часа.
Оснащение рабочего места: инструкционные карты, конспект.
Ход работы.
1.Выполнить следующие действия:
1. Начертите на плоскости графическое изображение графа, постройте его матрицы инциденции и смежности. Определите число его ребер. Найдите его цикломатическое число.
1 вариант.
| № ребра | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Вершины | А | А | В | В | С | С | D | E | E | G | B | G |
| Вершины | B | B | C | C | D | F | E | F | G | F | F | A |
2 вариант.
| № ребра | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Вершины | E | A | D | B | C | C | D | E | E | G | B | G |
| Вершины | E | B | D | C | D | F | E | F | G | F | F | A |
3 вариант.
| № ребра | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Вершины | E | A | D | B | C | E | D | E | E | D | B | G |
| Вершины | E | B | D | C | D | D | E | F | G | D | F | A |
4 вариант.
| № ребра | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Вершины | A | B | C | D | E | F | G | A | C | B | C | C |
| Вершины | B | C | D | E | F | G | A | E | F | E | E | F |
2. Выполните следующие действия.
| № вар. | Дуги графа U |
| 1 | { (0,1), (0,2), (0,5), (1,0), (1,0), (1,4), (1,5), (2,1), (2,3), (2,5), (3,0), (3,3), (3,4), (3,5), (4,1), (4,0), (4,4), (5,0), (5,1), (5,2), (5,4), (5,5) } |
| 2 | { (0,0), (0,2), (0,4), (1,2), (1,3), (1,5), (2,2), (2,4), (2,5), (3,0), (3,2), (3,3), (3,5), (4,0), (4,1), (4,3), (4,5), (5,0), (5,2), (5,3), (5,4), (5,4) } |
| 3 | { (0,0), (0,3), (0,5), (1,1), (1,3), (1,5), (2,2), (2,3), (2,3), (3,0), (3,1), (3,4), (3,5), (4,0), (4,2), (4,5), (5,0), (5,2), (5,3), (5,4), (5,4), (5,5) } |
| 4 | { (0,2), (0,4), (0,5), (1,1), (1,3), (1,5), (1,5), (2,0), (2,3), (2,4), (2,5), (3,2), (3,4), (3,5), (3,5), (4,1), (4,2), (4,4), (4,5), (5,0), (5,2), (5,3) } |
| 5 | { (0,3), (0,5), (1,1), (1,3), (1,5), (1,5), (2,0), (2,4), (2,5), (3,0), (3,1), (3,2), (3,4), (3,5), (3,5), (4,1), (4,2), (4,4), (4,5), (5,0), (5,2), (5,3) } |
| 6 | { (0,0), (0,2), (0,4), (0,5), (1,2), (1,4), (1,5), (2,0), (2,2), (2,5), (2,5), (3,0), (3,1), (3,3), (3,5), (3,5), (4,1), (4,3), (4,5), (5,0), (5,3), (5,5) } |
| 7 | { (0,0), (0,1), (0,5), (1,3), (1,5), (1,5), (2,0), (2,4), (2,5), (3,0), (3,0), (3,2), (3,4), (3,5), (4,0), (4,2), (4,5), (4,5), (5,1), (5,2), (5,3), (5,5) } |
| 8 | { (0,1), (0,4), (0,6), (1,1), (1,3), (1,4), (1,5), (2,0), (2,4), (2,5), (2,5), (3,0), (3,1), (3,3), (3,5), (4,2), (4,3), (4,5), (5,1), (5,3), (5,4), (5,4) } |
| 9 | { (0,0), (0,2), (0,5), (1,0), (1,1), (1,4), (1,5), (2,1), (2,5), (2,5), (3,0), (3,3), (3,4), (3,5), (4,0), (4,1), (4,5), (5,0), (5,1), (5,3), (5,4), (5,5) } |
| 10 | { (0,2), (0,4), (0,5), (1,1), (1,2), (1,4), (1,5), (2,0), (2,3), (2,5), (2,5), (3,0), (3,0), (3,1), (3,5), (4,2), (4,4), (4,5), (5,1), (5,3), (5,4), (5,5) } |
В соответствии с вариантом задания, приведенным в таблице, построить геометрическое и матричное представление графа.
1. Определить инцидентные ребра для множества вершин {1, 3, 5}.
2. Для множества вершин {0, 1, 2, 3} выделить подграф и из него получить полный и обыкновенный графы.
3. Выделить 4 элементарных контура графа.
Контрольные вопросы:
- Что такое матрица инциденции? Сформулируйте правило задания графа при помощи матрицы инциденции.
- Что такое матрица смежности? Сформулируйте правило задания графа при помощи матрицы смежности.
- Что такое список ребер? Сформулируйте правило задания графа при помощи списка ребер.
- Что такое маршрут, контур.
- Что такое цикл? Эйлеров цикл?
Литература: Ерош И.Л., Сергеев М.Б., Соловьев Н.В. Дискретная математика: Учебное пособие/ СПбГУАП. СПб., 2005. 144с.:ил.
С уважением, автор блога «Персональный сайт учителя информатики»
