Дискретная математика

Рефераты, курсовые, дипломные, контрольные (предпросмотр)

Тип: Курсовая работа. Файл: Word (.doc) в архиве zip. Категория: Математика
Адрес этого реферата http://referat-kursovaya.repetitor.info/?essayId=20096 или
Загрузить
В режиме предпросмотра не отображаются таблицы, графики и иллюстрации. Для получения полной версии нажмите кнопку «Загрузить». Рефераты, контрольные, дипломные, курсовые работы предоставляются в ознакомительных целях, не для плагиата.
Страница 2 из 4 [Всего 4 записей]« 1 2 3 4 »

Базисным графом называется ориентированный частичный граф, образованный из исходного удалением петель и замыкающих дуг.

Связность графа

В общем случае граф может быть представлен несколькими отдельными графами, не имеющими общих дуг. Тогда граф G(X,U) называется несвязным, а каждый из составляющих его графов G1 , G2 ,...Gn - компонентами связности. Граф называется связным, когда каждую его вершину можно соединить с любой другой его вершиной некоторой цепью.

Операции над графами

1. Объединение графов

G3(X3,Гх3) = G1(X1,Г1х1) - G2(X2,Г2х2), где X3=X1?X2, а Гx3=Г1x1?Г2x2

Пример (Рис 1.1).

2. Пересечение графов

G3(X3,Гх3) = G1(X1,Г1х1) ?G2(X2,Г2х2), где X3=X1? X2, а Гx3=Г1x1?Г2x2

Пример (рис 1.2).

4. Прямое (декартово) произведение графов.

Прямым произведением множеств Х{x1.......xn} и Y называется множество Z, элементами которого являются всевозможные пары вида xi , yj , где xi?X, yj?Y. Обозначают: Z=X x Y.

G3(X3,Гх3) = G1(X1,Г1х1) - G2(X2,Г2х2), где X3=X1?X2, а Гx3=Г1х1?Г2х2

Пример. (рис 2.3)

G1(X,Гх)=G1(X1,Гх1) G2(Y,Гy)= G2(X2,Гх2)

X={x1 x2 x3 } Y={y1 y2}

Гх1=0 Гу1={y1 y1}

Гх2={x1 x3} Гу2={y1}

Гх3=0

Z=X x Y={x1 y1, x1y2, x2y1, x2y2, x3y1, x3y2}

Z={z1 z2 z3 z4 z5 z6}

7. Расширение графа.

Расширение графа - это превращение, линии, соединяющей любые две вершины графа в элементарный путь введением новых промежуточных вершин на этой линии.

8. Сжатие графа.

Сжатие графа - это превращение элементарного пути, соединяющего две любые вершины графа, в линию.

9. Стягивание графа.

Если граф содержит вершины Х1 и Y1 , то операцией стягивания называется исключение всех дуг между вершинами Х1 и Y1 и превращение всех вершин в одну общую вершину Х.

Некоторые числа теории графов

Пусть существует мультиграф с b вершинами, p ребрами, и R компонентами связности, тогда цикломатическое число мультиграфа определяется равенством:

V= p-b+R

Матрицы для графов

Матрицей смежности графа G(X,Гх), содержащего n вершин называется квадратная бинарная матрица А(G) n x n , c нулями на диагонали. Число единиц в строке равно степени соответствующей вершины.

Матрицей инциденций ориентированного графа G(X,U) называется прямоугольная матрица порядка [m x n] n - мощность множества Х, m - мощность множества U. Каждый элемент которой определяется следующим образом:

Пример.

Построим матрицы смежности (М1) и инциденций (М2) для графа G(X,U) (рис 2.1).

Дополнительная матрица графа G(X,U) представляет собой квадратную матрицу А1 , которая получается из матрицы смежности этого графа путем замены всех нулей единицами и наоборот.

Деревья и прадеревья

Деревом называется неориентированный связный граф с числом вершин не менее двух, не содержащий петель и циклов. Вершины, инцидентные только одной дуге дерева, называются висячими.

Прадрево - ориентированное дерево.

Корень прадерева - вершина у которой Р+(х)=0.

Календарное планирование программ сетевыми методами

Сетью называется конечный граф G(X,Y) , без циклов и петель, ориентированный в одном общем направлении от вершин V, являющимися входами графа, к вершинам W, являющимися выходами.

Сетевое планирование и управление программами включает три основных этапа: структурное планирование, календарное планирование и оперативное управление.

Этап структурного планирования начинается с разбиения программы на четко определенные операции. Затем определяются оценки продолжительности операций и строится сетевая модель (сетевой график, стрелочная диаграмма), каждая дуга (стрелка) которой отображает работу. Вся сетевая модель в целом является графическим представлением взаимосвязей операций программы. Построение сетевой модели на этапе структурного планирования позволяет детально проанализировать все операции и внести улучшения в структуру программы еще до начала ее реализации. Однако еще более существенную роль играет использование сетевой модели для разработки календарного плана выполнения программы.

Конечной целью этапа календарного планирования является построение календарного графика, определяющего моменты начала и окончания каждой операции, а также ее взаимосвязи с другими операциями программы. Кроме того, календарный график должен давать возможность выявлять критические операции (с точки зрения времени), которым необходимо уделять особое внимание, чтобы закончить программу в директивный срок. Что касается некритических операций, то календарный план должен позволять определять их резервы времени, которые можно выгодно использовать при задержке выполнения таких операций или с позиций эффективного использования ресурсов.

Заключительным этапом является оперативное управление процессом реализации программы. Этот этап включает использование сетевой модели и календарного графика для составления периодических отчетов о ходе выполнения программы. Сетевая модель подвергается анализу и в случае необходимости корректируется. В этом случае разрабатывается новый календарный план выполнения остальной части программы.

Сетевая модель

Сетевая модель отображает взаимосвязи между операциями и порядок их выполнения (отношение упорядочения или следования) Как правило, для представления операции используется стрелка (ориентированная дуга), направление которой соответствует процессу реализации программы во времени. Отношение упорядоченное между операциями задается с помощью событий. Событие определяется как момент времени, когда завершаются одни операции и начинаются другие. Начальная и конечная точки любой операции описываются, таким образом, парой событий, которые обычно называют начальным событием и конечным событием. Операции, выходящие из некоторого события, не могут начаться, пока не будут завершены все операции, входящие в это событие. По принятой в СПУ терминологии каждая операция представляется ориентировано дугой, а каждое событие - узлом (вершиной). Не требуется, что длина дуги была пропорциональна продолжительности операции, а графическое изображение дуг не обязательно должно представлять прямолинейный отрезок.

На рис. 3.1 а приведен типичный пример графического отображения операции i, j с начальным событием i и конечным событием j. На рис. 3.1 б показан другой пример, из которого видно, что для возможности начала операции (3, 4) требуется завершение операций (1,3) и (2, 3). Протекание операций во времени задается порядком нумерации событий, причем номер начального события всегда меньше номера конечного. Такой способ нумерации особенно удобен выполнении вычислений на ЭВМ.

Правила построения сетевой модели

Правило 1. Каждая операция в сети представляется одной и только одной дугой (стрелкой). Ни одна из операций не должна появляться в модели дважды. При этом следует различать случай, когда какая-либо операция разбивается на части; тогда каждая часть изображается отдельной дугой. Так, например, прокладку трубопровода можно расчленить на прокладку отдельных секций и рассматривать прокладку каждой секции как самостоятельную операцию.

Правило 2. Ни одна пара операций не должна определяться одинаковыми начальным и конечным событиями. Возможность неоднозначного определения операций через события появляется в случае, когда две или большее число операций допустимо выполнять одновременно. Пример этого случая приведен на рис. 3.2 а, где операции А' и В имеют одинаковые начальное и конечное события. Чтобы исключить такую "ошибку" между А и конечным (начальным) событием или между В и конечным (начальным) событием, вводится фиктивная операция D . Рис. 3.2 б иллюстрирует различные варианты введения такой фиктивной операции D. В результате операции А и В определяются теперь однозначно парой событий, отличающихся либо номером начального, либо номером конечного события. Следует обратить внимание на то, что фиктивные операции не требуют затрат ни времени, ни ресурсов.

RSSСтраница 2 из 4 [Всего 4 записей]« 1 2 3 4 »


При любом использовании материалов сайта обязательна гиперссылка на сайт «Репетитор».
Разработка и Дизайн компании Awelan
www.megastock.ru
Проверить аттестат