«

»

Дек 19

Дискретная математика. Практическая работа №2

Добрый день, уважаемые читатели блога!

Эта статья предназначена для студентов специальности 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 элементарных контура графа.

 

Контрольные вопросы:

 

  1. Что такое матрица инциденции? Сформулируйте правило задания графа при помощи матрицы инциденции.
  2. Что такое матрица смежности? Сформулируйте правило задания графа при помощи матрицы смежности.
  3. Что такое список ребер? Сформулируйте правило задания графа при помощи списка ребер.
  1. Что такое маршрут, контур.
  2. Что такое цикл? Эйлеров цикл?

Литература: Ерош И.Л., Сергеев М.Б., Соловьев Н.В. Дискретная математика: Учебное пособие/ СПбГУАП. СПб., 2005. 144с.:ил.

С уважением, автор блога «Персональный сайт учителя информатики»

Tulova_Ulya

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>