Методические указания к выполнению лабораторных работ по курсу "Дискретная математика" пенза 2004 (стр. 2 из 6)

Рис. 1. Объединение графов G₁, G₂

Объединение графов G₁ и G₂ называется дизъюнктным, если V₁

V₂ =

. При дизъюнктном объединении никакие два из объединяемых графов не должны иметь общих вершин.

Пересечение. Граф G называется пересечением графов G₁, G₂, если V_G = V₁

V₂ и U_G = U₁

U₂ (риc.2). Операция "пересечения" записывается следующим образом: G = G₁

G₂.

Рис.2. Пересечение графов G₁, G₂.

Декартово произведение. Граф G называется декартовым произведением графов G₁ и G₂ если V_G = V₁

V₂ —декартово произведение множеств вершин графов G₁, G₂, а множество ребер U_c задается следующим образом: вершины (z_i, v_k) и (z_j, v_l) смежны в графе G тогда и только тогда, когда z_i = z_j(i = j), a v_k и v_l смежны в G₂ или v_k = v_l(k = l), смежны в графе G₁ (см. рис.3).

Рис. 3. Декартово произведение графов G₁, G₂

Кольцевая сумма графов представляет граф, который не имеет изолированных вершин и состоит из ребер, присутствующих либо в первом исходном графе, либо во втором. Кольцевая сумма определяется следующим соотношением: G = G₁

G₂ (рис.4).

Рис.4. Кольцевая сумма графов G₁, G₂

Лабораторное задание

1. Выполните генерацию матриц M₁, М₂ смежности неориентированных помеченных графой G₁, G₂. Метки вершин выберите из подмножества натуральных чисел {1, 2, …, n}. Порядок графов, определяется преподавателем. Вычислите матрицу смежности дополнительного графа (дополнения)

G₁. Порядок графа п определяется преподавателем.

2. Вычислите матрицы смежности подграфов Н, Q графа G₁(

G₁).

Например:

H = G₁ - v_i, i = 1, 2,..., n;

Q = G₁ - v_i - v_j, i = 1, 2,..., n, i

j.

3. Выполните операцию отождествления вершин (стягивания ребра, расщепления вершины) в графе G₁(

G₁), Номера выбираемых для выполнения операции двух вершин (вершины) согласуйте с преподавателем.

4. Выполните операцию объединения (пересечения, кольцевой суммы) графов G = G₁

G₂ (G = G₁ G₂, G = G₁ G₂).

5. Выполните операцию декартова произведения графов G = G₁ X G₂, i = 1,2

Содержание отчета

1. Матричные и графические представления графов G₁(

G₁),Н,Q,,G₂, G₃.

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

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

1. Задан неориентированный граф G. В графе удаляются вершина и два ребра. Существенна ли последовательность выполнения операций?

2. Как выглядит колода P(G) п — вершинного графа G, если все подграфы, входящие в колоду, выписать следующим образом:

G₁ = G - v_i, i = 1, 2, ..., n?

3. К = {{1, 2}; {1, 2}} — полный двухвершинный граф, Q = ({{1,2,3,4}; {{1, 2}; {2, 3}; {3, 4}; {4, 1}} - двумерный куб. Верно ли, что граф R = К

Q - трехмерный куб?

4. Графы H = H₁

H₂ и Q являются подграфами полного n-вершинного графа. Выполняется ли для них соотношение

H

Q = (H₁

H₂)

Q = H₁

Q

H₂

Q?

Лабораторная работа № 3

АНАЛИЗ СВОЙСТВ СЕТЕЙ ПЕТРИ

Цель работы - изучение форм представления сетей Петри и их анализ в среде системы компьютерной математики Mathcad.

Основные понятия и определения

Cеть Петри представляется четверткой

, где – конечное множество позиций , – конечное множество переходов , – отображение множества переходов в комплекты входных позиций (входная функция), – отображение множества переходов в комплекты выходных позиций (выходная функция). Множество позиций и переходов не пересекаются . Позиция является входной позицией перехода , если . Позиция является выходной позицией перехода , если . Входы и выходы переходов представляют собой комплекты позиций. Запись обозначает число появлений позиции в комплекте . Для сети, приведенной на рис. 5, и . Входная и выходная функции имеют вид:

;	;
;	;
;	;
;	.

Маркировка сети Петри есть процесс присвоения фишек (маркеров) позициям. Маркировка задается функцией, отображающей множество позиций

в множество неотрицательных целых чисел . Маркировка может быть определена как вектор . На графе фишки изображаются маленькими точками в кружке позиции. Состояние сети Петри определяется её маркировкой. Запуск разрешенного перехода изменяет состояние сети Петри посредством изменения маркировки.