Контрольная работа по дисциплине "Дискретная математики"

Автономная некоммерческая организация высшего профессионального образования

«СЕВЕРО-ЗАПАДНЫЙ ОТКРЫТЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

 

Дисциплина: "Информатика"

 

КОНТРОЛЬНАЯ РАБОТА

 

 

Ф.И.О. студента Удовиченко Тина Витальевна

(Фамилия, Имя, Отчество полностью)

Направление подготовки: 08100  «Дискретной математике»

Шифр студента ____________________

Вариант №9

 

Дата выполнения работы___27.05.2014_____

(число, месяц, год)

Руководитель работы________________________________________________________

(Ф.И.О. преподавателя)

 

 

 

 

 

Санкт-Петербург

20_14_г.

1. Элементы теории графов 

1. Пусть на плоскости  даны n точек S1, S2,…,Sn – вершины. И пусть они

соединены линиями (прямыми или нет), и необязательно каждая пара. Эти

линии – рёбра. Полученная фигура называется графом.

2. Если на рёбрах выбраны  направления, граф называется 

ориентированным или орграфом, а рёбра – дугами (рис. 1).

3. Граф называется полным, если любая пара вершин соединена  дугой, в

противном случае – неполным.

4. Совокупность дуг, соединяющих две вершины Sk и Sm называется

путем из Sk в Sm.

Если начало и конец пути совпадают, то такой путь называется циклом.

 Т.е. S1S2S3 – путь, а S1S2S3S1 – цикл.

 5. Граф наз. связанным, если существует хотя бы один путь,

соединяющий любые две его вершины. В противном случае – несвязанный.

 

Рис.1. Примеры графов

6. Связный граф, не содержащий  циклов наз. деревом. Если у дерева 

выделена одна вершина, она называется корнем дерева, а сам граф в этом

случае будет корневым деревом (рис.2).

7. Связный подграф исходного  графа, который не содержит циклов, и в

котором путь от корня до каждой из вершин является наименьшим из всех

возможных, называется остовным деревом.

 

 

 

 

1.1. Задачи на графах 

 Типичными задачами, решаемыми с помощью графов являются

1. О нанесении проводников  на плату: нанести на печатную плату некоторую схему проводников так, чтобы любые два из них не пересекались между собой ни в каких точках, кроме заданных.

2. Об обеспечении максимального  транспортного потока между двумя 

заданными пунктами.

3. Задача о построении  кратчайшего пути.

Рассмотрим ее подробно.

 Пусть задан граф G (рис. 3) и задана таблица расстояний  между его

вершинами. Эта таблица наз. матрицей весов. Если все расстояния в графе

равны 1, то полученная матрица наз. матрицей смежностей.

 

 

 

Задача ставится так: найти кратчайшее расстояние Х1→Х6.

Используем для решения т.н. алгоритм Дейкстры, в котором по

определенному правилу вершинам присваивают временные и постоянные

метки и также по определенному правилу заменяют временные метки на

постоянные. Процесс состоит из шагов, каждый из которых включает в себя

три действия и заканчивается, когда все метки станут постоянными.

Действия на каждом шаге:

1. Первой из выделенных вершин  присваивают постоянную метку 

l*(x1) = 0, где символ * означает, что это значение относится к постоянной

метке, а всем остальным вершинам – временные метки l(xi) = ∞, i = 2, 3, 4, 5, 6.  2. Рассматривают множество вершин Г(xi) = {xj

, …, xk}, соседних с той, которая имеет постоянную метку, и вычисляют для них новые временные

метки по правилу (для xj):

L (xj) = min {l(xj), l*(xi) + rij}, где l(xj) – старая временная метка вершины

xj, а rij – расстояние от xi

  до xj. 3. Выбирают min из всех временных меток, которая становится

постоянной, и делают следующий шаг.

 

 

 

 

 

 

 

 

Здесь видим, что сумма совпадает с постоянной

меткой вершины Х3, а для Х3, очевидно,

предшествующей вершиной будет Х1. Таким

образом, кратчайший путь оказывается таким:

 

 

 

2. Провести  в ДНФ все возможные операции  неполного склеивания. Их 

удобно проводить в два этапа: сначала все возможные операции

полного склеивания, а затем выписать результаты полного склеивания

в начале ДНФ, соединив их между собой и с остальными членами ДНФ

знаками дизъюнкции (это и будет неполное склеивание).

3. Провести  все возможные операции поглощения, в результате чего 

получим ДНФ, состоящую из элементарных конъюнкций ранга, на

единицу меньшего.

4. В полученной  ДНФ провести все возможные  операции склеивания и 

поглощения в соответствии с п.3) и 4). В результате получим ДНФ,

состоящую из элементарных конъюнкций ранга ещё на единицу

меньшего.

Описанную процедуру следует проводить до тех пор, пока это будет

возможно. Полученная в итоге ДНФ и будет сокращённой. Образующие её

элементарные конъюнкции называются простыми импликантами функции f .