СКАЧАТЬ:  zadacha2-2.zip [63,19 Kb] (cкачиваний: 25)

ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ

по дисциплине:

«МОДЕЛИРОВАНИЕ СИСТЕМ»

                               «Порядковая функция на графе»

Практическая часть

Рис.1. Вид неупорядоченного графа

Составляем матрицу смежности анализируемого графа (табл. 1)

Таблица 1

                                   А=

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

Результаты преобразований сведены в таблицу 2

Таблица 2

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

Строим матрицу смежности упорядоченного графа.(таблица 3)

Таблица 3

                              А=

Задача упорядочения может быть решена с помощью матрицы инциденций

Таблица 4

Рис.2. Рис.1. Вид упорядоченного графа

Рис.3. Рис.1. Вид неупорядоченного графа

Первое вычёркивание.  Вычеркнуты вершины 5 и7 (таблица 5).

 - обозначение пустой клетки.

Таблица 5

Второе вычёркивание.  Вычеркнуты вершины 1и10 (таблица 6)

Таблица 6

Третье вычёркивание.  Вычеркнуты вершины 8и 9 (таблица 7).

Таблица 7

Четвёртое вычёркивание.  Вычеркнуты вершины 6 (таблица 8).

Таблица 8

Полученный результат использования алгоритма вычёркивания сводим в таблицу 9

Таблица 9