Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Курсовая работа: Построение матрицы достижимости

Название: Построение матрицы достижимости
Раздел: Рефераты по математике
Тип: курсовая работа Добавлен 07:29:59 23 апреля 2011 Похожие работы
Просмотров: 1782 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Государственное образовательное учреждение

высшего профессионального образования

Уфимский государственный авиационный технический университет

Курсовая работа

по Дискретной математике

на тему: Построение матрицы достижимости

Уфа 2006 г.


Введение

Цель работы:

Разработать программу на языке TURBOPASCAL, осуществляющую вычисление матрицы достижимости.

Постановка задачи:

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


Матрицы достижимости и связности

Пусть A(D) – матрица смежности ориентированного псевдографа D=(V,X) (или псевдографа G=(V,X)), где V={v1,…, vn}. Обозначим через Ak=[a(k)ij] k-ю степень матрицы смежности A(D).

Утверждение. Элемент a(k)ij матрицы Ak ориентированного псевдографа D=(V,X) (псевдографа G=(V,X)) равен числу всех путей (маршрутов) длины k из vi в vj.

Доказательство:

Для k=1 очевидно в силу построения матрицы A(D).

Пусть это справедливо для n=k-1. Т.е. в матрице Ak-1 в i-той строке на l-том месте стоит число, означающее кол-во маршрутов из vi в vl длины k−1. Столбец под номером j матрицы A содержит числа, означающие кол-во дуг (ребер) из vl в vj (l-номер строки). Тогда скалярное произведение i-той строки матрицы Ak-1 на j-тый столбец матрицы A равен сумме произведений. Каждое произведение означает кол-во путей из vi в vj, проходящих через vl на предпоследнем шаге. В сумме получается общее кол-во.

Утверждение. Для того, чтобы n-вершинный орграф D с матрицей смежности A=A(D) имел хотя бы один контур, - чтобы матрица K=A2+A3+… An имела ненулевые диагональные элементы (следствие предыдущего).

Пусть ρ-отношение достижимости на множестве V всех вершин (неориентированного) графа G. (либо v=w, либо существует маршрут, соединяющий v и w).

Тогда

1) ρ-отношение эквивалентности;

2) vρw - вершины v,w принадлежат одной компоненте связности;

3) для любого класса эквивалентности V1 псевдограф G1, порожденный множеством V1, является компонентой связности псевдографа G. Для орграфа: Пусть 1-отношение достижимости на множестве V всех вершин ориентированного псевдографа D. Пусть ρ2-отношение двусторонней достижимости на множестве V. (ρ2=ρ1∩ρ1-1). Тогда

1) ρ1 - рефлексивно, транзитивно;

2) ρ2 – эквивалентность на V;

3) vρ2w - когда вершины v,w принадлежат одной компоненте сильной связности;

4) для любого класса эквивалентности V1 ориент. псевдограф D1, порожденный множеством V1, является компонентой связности ор. псевдографа G.

Число компонент связности орграфа D обозначается P(D). (для неор. - P(G).

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

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

Утверждение. Если D' – орграф, полученный в результате удаления нескольких вершин из орграфа D, то A(D') получается из A(D) в результате удаления строк и столбцов, соответствующих удаленным вершинам. (Для неор. графа то же самое).

Определение. Матрицей достижимости орграфа D называется квадратная матрица T(D)=[tij] порядка n, элементы которой равны

- tij=1, если vj достижима изvi,

- tij=0, в противном случае.

Определение. Матрицей сильной связности орграфа D называется квадратная матрица S(D)=[sij] порядка n, элементы которой равны

- sij=1, если vj достижима изvi и viдостижима изvj,

- sij=0, в противном случае.

Определение. Матрицей связности графа G называется квадратная матрица S(G)=[sij] порядка n, элементы которой равны

- sij=1, если существует маршрут, соединяющий vj и vi,

- sij=0, в противном случае.

Утверждение

Пусть G=(V,X) – граф, V={v1,…, vn}, A(G) – его матрица смежности. Тогда

S(G)=sign[E+A+A2+A3+… An-1] (E- единичнаяматрицапорядка n). (Следует из предыдущего).

Алгоритм выделения компонент сильной связности

1. Присваиваем p=1, S1=S(D).

2. Включаем в множество вершин Vp компоненты сильной связности Dp вершины, соответствующие единицам первой строки матрицы Sp. В качестве матрицы A(Dp) возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из Vp.

3. Вычеркиваем из Sp строки и столбцы, соответствующие вершинам из Vp. Если не остается ни одной строки (и столбца), то p- кол-во компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу Sp+1, присваиваем p:=p+1 и переходим к п. 2.

Текст программы (с комментариями)

PROGRAMG_r_a_p_h;

Uses CRT;

const MaxNodes = 5; { Количество вершин в графе }

type NodePtr = 1..MaxNodes;

Element = 0..1;

AdjMatrix = Array [NodePtr,NodePtr] of Element;

var Adj : AdjMatrix; { Матрицасмежностей }

Path: AdjMatrix; { Матрицадостижимости }

i,j : NodePtr;

PROCEDURE P_r_o_d (A,B: AdjMatrix; var C: AdjMatrix);

{ Матрица C получает значение булевского }

{ произведения матриц A и B }

var Val : Element;

i,j,k: Integer;

BEGIN

For i:=1 to MaxNodes do

For j:=1 to MaxNodes do begin

Val:=0;

For k:=1 to MaxNodes do

Val:=Val OR (A[i,k] AND B[k,j]);

C[i,j]:=Val end

END;

PROCEDURE T_r_a_n_s_C_l_o_s_e (Adj: AdjMatrix; var Path: AdjMatrix);

{ Вычислени матрицы достижимости Path по }

{ заданной матрицы смежностей Adj }

var i,j,k : NodePtr;

NewProd: AdjMatrix;

AdjProd: AdjMatrix; BEGIN

AdjProd:=Adj; Path:=Adj;

For i:=1 to MaxNodes-1 do begin

P_r_o_d (AdjProd,Adj,NewProd);

For j:=1 to MaxNodes do For k:=1 to MaxNodes do

Path[j,k]:=Path[j,k] OR NewProd[j,k];

AdjProd:=NewProd

end

END;

BEGIN

clrscr;

{ Ввод матрицы смежностей заданного графа }

WriteLn ('Вводите элементы матрицы смежностей по строкам:');

For i:=1 to MaxNodes do

For j:=1 to MaxNodes do begin

Write ('‚Введите Adj[',i,',',j, ']: '); ReadLn (Adj[i,j]) end;

{ Вычисление и вывод матрицы достижимости }

T_r_a_n_s_C_l_o_s_e (Adj,Path);

WriteLn ('Матрицадостижимости: ');

For i:=1 to MaxNodes do begin For j:=1 to MaxNodes do if i=j then Path[i,j]:=1; end;

For i:=1 to MaxNodes do begin For j:=1 to MaxNodes do Write (Path[i,j],' '); WriteLn end;

readkey;

END.


Блок – схемы программы



Подпрограмма, где матрица С получает значение булевского произведения матриц А и В.


Подпрограмма для вычисления матрицы достижимости Path по заданной матрицы смежности Adj.


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

Тест 1

Вводите элементы матрицы смежностей по строкам:

Введите Adj[1,1]: 0

Введите Adj[1,2]: 0

Введите Adj[1,3]: 1

Введите Adj[1,4]: 0

Введите Adj[1,5]: 0

Введите Adj[2,1]: 0

Введите Adj[2,2]: 0

Введите Adj[2,3]: 0

Введите Adj[2,4]: 0

Введите Adj[2,5]: 0

Введите Adj[3,1]: 0

Введите Adj[3,2]: 1

Введите Adj[3,3]: 0

Введите Adj[3,4]: 1

Введите Adj[3,5]: 1

Введите Adj[4,1]: 0

Введите Adj[4,2]: 1

Введите Adj[4,3]: 0

Введите Adj[4,4]: 0

Введите Adj[4,5]: 0

Введите Adj[5,1]: 1

Введите Adj[5,2]: 0

Введите Adj[5,3]: 0

Введите Adj[5,4]: 1

Введите Adj[5,5]: 0


Матрица достижимости:

1 1 1 1 1

0 1 0 0 0

1 1 1 1 1

0 1 0 1 0

1 1 1 1 1

Тест 2

Вводите элементы матрицы смежностей по стро-кам:

Введите Adj[1,1]: 0

Введите Adj[1,2]: 1

Введите Adj[1,3]: 0

Введите Adj[1,4]: 1

Введите Adj[1,5]: 0

Введите Adj[2,1]: 0

Введите Adj[2,2]: 0

Введите Adj[2,3]: 0

Введите Adj[2,4]: 0

Введите Adj[2,5]: 0

Введите Adj[3,1]: 1

Введите Adj[3,2]: 1

Введите Adj[3,3]: 0

Введите Adj[3,4]: 0

Введите Adj[3,5]: 0

Введите Adj[4,1]: 0

Введите Adj[4,2]: 0

Введите Adj[4,3]: 1

Введите Adj[4,4]: 0

Введите Adj[4,5]: 0

Введите Adj[5,1]: 1

Введите Adj[5,2]: 0

Введите Adj[5,3]: 0

Введите Adj[5,4]: 1

Введите Adj[5,5]: 0

Матрица достижимости:

1 1 1 1 0

0 1 0 0 0

1 1 1 1 0

1 1 1 1 0

1 1 1 1 1


Заключение

В результате выполнения курсовой работы была разработана программа для вычисления матрицы достижимости. В работе были решены все поставленные перед нами задачи: теоретическое объяснение принципа вычисления матрицы достижимости; представление текста программы с комментариями, а также представления ее в виде блок – схем; проверка правильности работы программы то есть представление результатов тестирования.

Программа написана на языкеTURBOPASCAL, однако может быть легко переписана на любой из современных языков программирования, так как приведены довольно простые алгоритмы. Были максимально предусмотрены все возможные ошибки, которые могут возникнуть при использовании данной программы.


Список использованной литературы

1. Нефедов В.Н., Осипова В.А. // Курс дискретной математики. // М.: МАИ, 1992.

2. Кузнецов О.П., Адельсон-Вельский Г.М. // Дискретная математика для инженера. // М.: Энергоатомиздат, 1988.

3. Кук Д., Бейз Г. // Компьютерная математика. // М. Наука, 1990.

4. Бронштейн Е.М. // Множества и функции. // Методические указания. Уфа: УГАТУ. 1988.

5. Житников В. П. // Конспект лекции по дискретной математике. // Уфа: УГАТУ. 2007.

6. Павловская Т. А. Щупак Ю. А. // Учебник по практическому программированию (Бейсик, С, Паскаль). // Санкт-Петербург. 2005.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений08:04:42 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
10:31:38 29 ноября 2015

Работы, похожие на Курсовая работа: Построение матрицы достижимости
Основы дискретной математики
Федеральное агентство по образованию Новомосковский институт (филиал) Государственного образовательного учреждения высшего профессионального ...
Тогда графом G (V, A) называется совокупность множества вершин и множества ребер.
2 получить задание по индивидуальному варианту в виде графа или матрицы смежности, в первом случае построить матрицу смежности, во втором - нарисовать граф;
Раздел: Рефераты по информатике, программированию
Тип: учебное пособие Просмотров: 4174 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Задача остовных деревьев в k-связном графе
... Молдавский Государственный Университет Кафедра Информатики и Дискретной Оптимизации Дипломная работа: "Задача остовных деревьев в k-связном графе"
Из классического результата теории графов - теоремы Менгераизвестно, что для любых двух вершин x и y графа G локальная реберная связность (x, y, G) равняется наибольшему количеству ...
Из ранее известных результатов "глобальным ананлогом" теоремы Менгера в некоторой степени является доказанный результат: в графе G с реберной связностью (G)k существуют k остовных ...
Раздел: Рефераты по математике
Тип: реферат Просмотров: 1728 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Эйлеровы и гамильтоновы графы
Министерство народного образования Республики Дагестан Дагестанский Государственный Университет Курсовая работа Программирование задач на графах ...
Если в графе G(V,E) c n вершинами (n = 3) выполняется условие d(v) = n/2 для любого v V, то граф G является гамильтоновым.
Возьмём произвольную пару вершин j,k. Исключим непосредственное ребро D[j,k]. С помощью алгоритма Дейкстры найдём кратчайшее расстояние между городами j,.,k. Пусть это расстояние ...
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 6749 Комментариев: 3 Похожие работы
Оценило: 1 человек Средний балл: 2 Оценка: неизвестно     Скачать
Орграфы, теория и применение
Федеральное агентство по образованию РФ Государственное образовательное учреждение высшего профессионального образования "Санкт-Петербургский ...
Орграф, называемый конъюнкцией D=Dl/\D2 двух орграфов Z)j и D2, имеет в качестве множества вершин K=V1XV2, и вершина u=(u1, ы2) смежна к вершине v=(v-L,v2) тогда и только тогда ...
1) D - бесконтурный орграф; (2) D* изоморфен D; (3) каждый маршрут орграфа D есть путь; (4) вершины орграфа D можно упорядочить таким образом, что матрица смежностей" A (D) будет ...
Раздел: Рефераты по математике
Тип: реферат Просмотров: 1147 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Разработка системы задач (алгоритмы-программы) по дискретной ...
Вятский Государственный Гуманитарный Университет Кафедра прикладной математики Курсовая работа по информатике Тема: Разработка системы упражнений и ...
Матрица смежности - это двумерный массив размерности N*N. 1, вершина с номером i смежна с вершиной с номером j, 0, вершина с номером i не смежна с вершиной с номером j
Ориентированный граф G=, s - вершина источник; матрица смежности A (A:array[1..n,1..n] of integer); для любых u, v$V вес дуги неотрицательный (А[u,v]>=0). Результат.
Раздел: Рефераты по информатике, программированию
Тип: реферат Просмотров: 570 Комментариев: 2 Похожие работы
Оценило: 2 человек Средний балл: 2.5 Оценка: неизвестно     Скачать
Теория симметрии молекул
Министерство общего и профессионального образования РФ Дипломная работа "Теория симметрии молекул" Содержание Введение Глава 1 Элементы теории групп ...
Назовем i-ой матрицей смежности Ai матрицу порядка, равного порядку группы G, строки и столбцы которой занумерованы элементами группы G, причем элементы матрицы Ai с номером (g, h ...
Определение 8. Квадратная матрица Р порядка d, (j, i)-м элементом которой является pi(j), называется первой собственной матрицей алгебры Боуза-Меснера А. Матрица Q=(gi(j)) такая ...
Раздел: Рефераты по химии
Тип: дипломная работа Просмотров: 673 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Биокерамика на основе фосфатов кальция
Российская академия наук Институт физико-химических проблем керамических материалов С.М. Баринов, В.С. Комлев Биокерамика на основе фосфатов кальция ...
162. Rau J.V., Nunziante Cesaro S., Ferro D., Barinov S.M., Fadeeva I.V. FTIR study of carbonate loss from carbonated apatite in the wide temperature range // J. Biomed.
276. Costantino P.D., Friedman C.D., Jones K., Chow L.C., Pelzer H.J., Sisson G.A. Hydroxyapatite cement // Archives of Otolaryngology - Head and Neck Surgery.
Раздел: Рефераты по химии
Тип: книга Просмотров: 5623 Комментариев: 2 Похожие работы
Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Все работы, похожие на Курсовая работа: Построение матрицы достижимости (747)

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(150580)
Комментарии (1836)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru