Результаты работы программы

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

Національний аерокосмічний університет ім. М.Є. Жуковського “ХАІ”

Кафедра 603

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

ТЕОРИЯ ГРАФОВ.

ПОРЯДКОВАЯ ФУНКЦИЯ НА ГРАФЕ

з дисципліни “Дискретні структури”

ХАІ.603.622П.13В.050103.126332.ПЗ

Виконав студент гр. 622П Бровко В.К.

________________ (№ групи) (П.І.Б)

(підпис, дата)

Перевірив:_______к.т.н. доц Труш Г.О.

(наукова ступінь, вчене звання)

_____________________________

(підпис, дата) (П.І.Б)

Цель работы: изучить понятие функции на графе; научиться находить порядковую функцию на графе методом Демукрона.

Задачи

1. Ознакомиться с приведенными теоретическими понятиями о порядковой функции на графе.

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

3. Решить вручную задачу поиска порядковой функции графа без контуров для графа своего варианта.

4. Написать программу (в произвольно выбранной среде программирования), которая реализует метод Декмукрона.

Вариант 1

Ручные вычисления

	X1	X2	X3	X4	X5	X6	X7
X1
X2
X3
X4
X5
X6
X7

Листинг программы

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace LR3

{

class Program

{

// Генерация массива

static private int[][] initArray()

{

int[][] mat = new int[7][];

mat[0] = new int[7] { 0, 1, 1, 0, 0, 0, 0 };

mat[1] = new int[7] { 0, 0, 0, 1, 0, 0, 0 };

mat[2] = new int[7] { 0, 1, 0, 1, 0, 1, 0 };

mat[3] = new int[7] { 0, 0, 0, 0, 1, 1, 1 };

mat[4] = new int[7] { 0, 0, 0, 0, 0, 0, 1 };

mat[5] = new int[7] { 0, 0, 0, 0, 0, 0, 0 };

mat[6] = new int[7] { 0, 0, 0, 0, 0, 1, 0 };

return mat;

}

// Вывод матрицы на экран

static private void outMatrix(int[][] x)

{

int i, j;

for (i = 0; i < x.Length; i++)

{

for (j = 0; j < x[i].Length; j++)

Console.Write(" " + x[i][j]);

Console.WriteLine();

}

Console.Write("\n");

}

// Вывод массива на экран

static void outArray(int[] x)

{

for (int i = 0; i < x.Length; i++)

if (x[i] >= 0)

Console.Write(x[i] + "\t");

else Console.Write("-\t");

}

// Сумма столбцов матрицы смежности

static int[] sumOfMatrix(int[][] a)

{

int[] x = new int[a[0].Length];

int i, j;

for (i = 0; i < a.Length; i++)

x[i] = 0;

for (i = 0; i < a.Length; i++)

for (j = 0; j < a[0].Length; j++)

x[i] += a[j][i];

return x;

}

static void Main(string[] args)

{

int[][] mat = initArray();

Console.WriteLine("Первоначальный граф (в виде матрицы смежности):");

outMatrix(mat);

//Console.WriteLine("Сумма строк матрицы:");

//outArray(layer);

int[] layer = sumOfMatrix(mat);

Console.Write("\n\nРасчитываем слои порядковой функции:\n");

int l = 0, n = 1;

List<string> res = new List<string>();

string r = "";

int i;

while (l < mat.Length)

{

r = "";

Console.Write("Шаг " + n++ + " : ");

outArray(layer);

Console.WriteLine();

for (i = 0; i < layer.Length; i++)

{

if (layer[i] == 0)

{

r += (i + 1) + " ";

layer[i]--;

l++;

}

else

layer[i]--;

}

res.Add(r);

}

Console.WriteLine("\nРезультат: порядковая функция выделенного графа имеет уровни:");

for (i = 0; i < res.Count; i++)

Console.WriteLine("Уровень : " + (i + 1) + "\t\t Вершины : " + res[i]);

Console.Read();

}

}

}

Результаты работы программы

Рис.1. Первый тестовый пример.

Выводы: Выполнив данную лабораторную работу, я изучил понятие функций на графе и научился находить порядковую функцию на графе методом Демукрона. После чего, реализовал программу на языке С# в программной среде Microsoft Visual Studio 2010.