Министерство высшего и среднего образования РГРТА Кафедра АиММ Курсовая работа по дисциплине дискретная математика по теме теория графов Выполнил студент группы 232 Прокофьева Анна Проверил Орлов Геннадий Сергеевич Рязань 2003 год Графом называется двойка вида GXG,PG,где XG некоторое непустое множество, PG подмножество декартового произведения
XG PG XG2. Элементы множества XG принято называть вершинами графа. Элементы множества PG принято называть дугами ориентированными дугами, или рбрами неориентированными дугами. Граф называется неориентированным, если его дуги не имеют ориентации. В противном случае граф будет ориентированным. 1.Преобразовать исходную матрицу в матрицу длин, включая соответствующие символы. Исходная матрица имеет вид 1 2 3 4 5 6 7 8 9 10 1 0 4 0 0 0 0 0 0 0 8 2 0 0 0 0 0 13 0 0 0 17 3 0 4 0 0 11 0 9 0 0 8 4 7 0 0 0 0 0 0 0 10 0 5 0 0 0 0 0 0 0 0 0 0 6 0 0 12 2 14 0 0 0 0 0 7 0 0 0 0 0 0 0 0 16 0 8 0 0 0 14 0 0 0 0 1 0 9 0 0 3 0 0 0 0 14 0 0 10 0 20 0 0 16 0 0 0 0 0
S19 Матрицей длин нагруженного графа G называется матрица SG SGsi,jni,j1, nXn, элементы которой определяются следующим соотношением Lxi,xj,если xi,xj PG Si,j , еслиxi,xjPG В таком случае матрица длин имеет вид 1 2 3 4 5 6 7 8 9 10 1 4 8 2 13 17 3 4 11 9 8 4 7 10 5 6 12 2 14 7 16 8 14 1 9 3 14 10 20 16 SG Сформировать матрицу смежности графа G. Матрицей смежности, по определению, называют матрицу, обозначаемую AG AGai,jni,j1, nXG, элементы которой определяются следующим соотношением 1,если xi,xj
PG ai,j 0, еслиxi,xj PG От матрицы длин, вообще говоря, перейти к матрице смежности довольно легко. Элемент матрицы аi,j1, если элемент si,j является конечным числом и аi,j0, если элемент si,j не является конечным числом. Матрица смежности будет выглядеть следующим образом 1 2 3 4 5 6 7 8 9 10 1 0 1 0 0 0 0 0 0 0 1 2 0 0 0 0 0 1 0 0 0 1 3 0 1 0 0 1 0 1 0 0 1 4 1 0 0 0 0 0 0 0 1 0 5 0 0 0 0 0 0 0 0 0 0 6 0 0 1 1 1 0 0 0 0 0 7 0 0 0 0 0 0 0 0 1 0 8 0 0 0 1 0 0 0 0 1 0 9 0 0 1 0 0 0 0 1 0 0 10 0 1 0 0 1 0 0 0 0 0 AG 3.Изобразить графически граф G см. далее 4.Сформировать матрицу инцидентности. Для составления матрицы инцидентности необходимо перенумеровать все дуги графа
G. Нумерация графа произведена в предыдущем задании. Матрицей инцидентности графа G называется матрица BG BGbi,ji1,n, j1,m, nXG mXG,состоящая из элементов, которые определяются следующим образом 1, если дуга Uj исходит из вершины xi Bi,j -1, если дуга Uj заходит в вершину xi 0, если дуга Uj не инцидентна вершине xi U1 U2 U3 U4 U5 U6 U7 U8
U9 U10 U11 U12 U13 U14 U15 U16 U17 U18 U19 U20 1 1 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 2 -1 0 1 1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 3 0 0 0 0 1 1 1 1 0 0 0 0 -1 0 0 0 -1 0 0 0 4 0 0 0 0 0 0 0 0 1 1 -0 В таком случае матрицу инцидентности данного графа можно записать 5.Игнорированием ориентации дуг перейти от ориентированного графа G к неориентированному графу G. Изобразить полученный граф G графически. 6.Сформировать матрицы смежности и инцидентности полученного
графа G . Матрица смежности неориентированного графа является симметрической и будет иметь вид 1 2 3 4 5 6 7 8 9 10 1 0 1 0 1 0 0 0 0 0 1 2 1 0 1 0 0 1 0 0 0 1 3 0 1 0 0 1 1 1 0 1 1 4 1 0 0 0 0 1 0 1 1 0 5 0 0 1 0 0 1 0 0 0 1 6 0 1 1 1 1 0 0 0 0 0 7 0 0 1 0 0 0 0 0 1 0 8 0 0 0 1 0 0 0 0 1 0 9 0 0 1 1 0 0 1 1 0 0 10 1 1 1 0 1 0 0 0 0 0 AG Матрицей инцидентности неориентированного графа, по определению, называется матрица BGbi,ji1,n, j1,m, nXG mXG,состоящая из элементов, которые определяются следующим образом 1, если j-ое ребро инцидентно i-ой вершине bi,j 0, в противном случае. Таким образом, матрица инцидентности неориентированного графа
G будет представлять собой следующую матрицу U1 U2 U3 U4 U5 U6 U7 U8 U9 U10 U11 U12 U13 U14 U15 U16 U17 U7.Найти компоненты сильной связности ориентированного графа G. Компонентами сильной связности графа G называются его сильно связные подграфы, не являющиеся собственными подграфами никакого другого сильно
связного подграфа графа G. В свою очередь, сильно связным графом называется ориентированный граф G, если для любых двух его вершин x и y , вершина x достижима из y, и вершина y достижима из x. Для нахождения компонент сильной связности воспользуемся соответствующим алгоритмом. Запишем матрицу сильной связности графа G. Матрицей сильной связности называется матрица DGn n, nXG, элементы которой определяются следующим образом 1, если xi и xj достижимы друг из друга
di,j 0 , если xi и xj не достижимы друг из друга В таком случае можно записать матрицу сильной связности следующим образом 1 Итак, применяя алгоритм, найдм компоненты сильной связности. 1 шаг. Положим p1. В качестве D1G возьмм матрицу DG. 2 шаг. Включаем во множество вершин XH1 вершины, соответствующие единицам первой строки матрицы D1G. В таком случае, XH1 1,2,3,4,6,7,8,9,10 В качестве матрицы
AH1 берм подматрицу матрицы AG, элементы которых находятся на пересечении строк и столбцов, соответствующих выбранным вершинам то есть вершинам из XH1 . Тогда 6 В таком случае, AH1 Итак, первая компонента сильной связности найдена. 3 шаг. Вычркиваем из матрицы D1G строки и столбцы, соответствующие вершинам из множества XH1 Тогда DH2 Так как матрицу достижимости ещ можно сформировать,
продолжим алгоритм Положим p2. 2 шаг. По всей видимости, XH25. Вершина 5 и является второй компонентой сильной связности. Дальше увеличивать параметр p невозможно. Итак, мы получили 2 компоненты сильной связности для данного графа G 8. Найти компоненты связности неориентированного графа G Компонентами связности неориентированного графа называются его связные компоненты, не являющиеся собственными
подграфами никакого другого связного подграфа данного графа. Неориентированный граф называется связным, если любые две вершины достижимы друг из друга. Найдм компоненты связности неориентированного графа G . Для этого найдм матрицу DG 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1 1 5 1 1 1 1 1 1 1 1 1 1 6 1 1 1 1 1 1 1 1 1 1 7 1 1 1 1 1 1 1 1 1 1 8 1 1 1 1 1 1 1 1 1 1 9 1 1 1 1 1 1 1 1 1 1 Так как в неориентированном графе G нет изолированных вершин, то, очевидно, что у этого графа есть только
одна компонента связности-это он сам. Итак, компонентой связности неориентированного графа G является граф G 9. Перечислить все пути в ориентированном графе G, состоящие из 4 дуг. Для решения задачи необходимо сформировать таблицу, состоящую из 10 строк и 10 столбцов, такую, что в i,j-ой ячейке будущей таблицы будет записано множество Пkxi,xjji,jk . Тогда данную таблицу можно представить в виде матрицы, размерности 1010 с элементами
ji,j k . Обозначим через Гk ji,j k матрицу таблицу с элементами ji,j k. Теперь запишем матрицу смежности графа G 1 2 3 4 5 6 7 8 9 10 1 0 1 0 0 0 0 0 0 0 1 2 0 0 0 0 0 1 0 0 0 1 3 0 1 0 0 1 0 1 0 0 1 4 1 0 0 0 0 0 0 0 1 0 5 0 0 0 0 0 0 0 0 0 0 6 0 0 1 1 1 0 0 0 0 0 7 0 0 0 0 0 0 0 0 1 0 8 0 0 0 1 0 0 0 0 1 0 9 0 0 1 0 0 0 0 1 0 0 10 0 1 0 0 1 0 0 0 0 0 AG По виду матрицы смежности графа G сформулируем первую таблицу Г1. 1 2 3 4 5 6 7 8 9 10 1 Ш 1,2 Ш Ш Ш Ш Ш Ш Ш 1,10 2 Ш Ш Ш Ш Ш 2,6 Ш Ш Ш 2,10 3 Ш 3,2 Ш Ш 3,5 Ш 3,7 Ш Ш 3,10 4 4,1
Ш Ш Ш Ш Ш Ш Ш 4,9 Ш 5 Ш Ш Ш Ш Ш Ш Ш Ш Ш Ш 6 Ш Ш 6,3 6,4 6,5 Ш Ш Ш Ш Ш 7 Ш Ш Ш Ш Ш Ш Ш Ш 7,9 Ш 8 Ш Ш Ш 8,4 Ш Ш Ш Ш 8,9 Ш 9 Ш Ш 9,3 Ш Ш Ш Ш 9,8 Ш Ш 10 Ш 10,2 Ш Ш 10,5 Ш Ш Ш Ш Ш Г1 Для того, чтобы получить таблицу Г2 необходимо над таблицей Г1 нарисовать АТG 1 2 3 4 5 6 7 8 9 10 1 0 0 0 1 0 0 0 0 0 0 2 1 0 1 0 0 0 0 0 0 1 3 0 0 0 0 0 1 0 0 1 0 4 0 0 0 0 0 1 0 1 0 0 5 0 0 1 0 0 1 0 0 0 1 6 0 1 0 0 0 0 0 0 0 0 7 0 0 1 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 1 0 9 0 0 0 1 0 0 1 1 0 0 10 1 1 1 0 0 0 0 0 0 0
АтG 1 2 3 4 5 6 7 8 9 10 1 Ш 1,2 Ш Ш Ш Ш Ш Ш Ш 1,10 2 Ш Ш Ш Ш Ш 2,6 Ш Ш Ш 2,10 3 Ш 3,2 Ш Ш 3,5 Ш 3,7 Ш Ш 3,10 4 4,1 Ш Ш Ш Ш Ш Ш Ш 4,9 Ш 5 Ш Ш Ш Ш Ш Ш Ш Ш Ш Ш 6 Ш Ш 6,3 6,4 6,5 Ш Ш Ш Ш Ш 7 Ш Ш Ш Ш Ш Ш Ш Ш 7,9 Ш 8 Ш Ш Ш 8,4 Ш Ш Ш Ш 8,9 Ш 9 Ш Ш 9,3 Ш Ш Ш Ш 9,8 Ш Ш 10 Ш 10,2 Ш Ш 10,5
Ш Ш Ш Ш Ш Г1 1 2 3 4 5 6 7 8 9 10 1 Ш 1,10,2 Ш Ш 1,10,5 1,2,6 Ш Ш Ш 1,2,10 2 Ш 2,10,2 2,6,3 2,6,4 2,6,5 2,10,5 Ш Ш Ш Ш Ш 3 Ш 3,10,2 Ш Ш 3,10,5 3,2,6 Ш Ш 3,7,9 3,2,10 4 Ш 4,1,2 4,9,3 Ш Ш Ш Ш 4,9,8 Ш 4,1,10 5 Ш Ш Ш Ш Ш Ш Ш Ш Ш Ш 6 6,4,1 6,3,2 Ш Ш 6,3,5 Ш 6,3,7 Ш 6,4,9 6,3,10 7
Ш Ш 7,9,3 Ш Ш Ш Ш 7,9,8 Ш Ш 8 8,4,1 Ш 8,9,3 Ш Ш Ш Ш 8,9,8 8,4,9 Ш 9 Ш 9,3,2 Ш 9,8,4 9,3,5 Ш 9,3,7 Ш 9,8,9 9,3,10 10 Ш Ш Ш Ш Ш 10,2,6 Ш Ш Ш 10,2,10 Итак, мы получили таблицу Г2. Пользуясь тем же методом, но используя уже таблицу Г2,получим таблицу Г3. 1 2 3 4 5 6 7 8 9 10 1 Ш 1,2,10,2 1,2,6,3 1,2,6,4 1,2,6,5 1,2,10,5 1,10,2,6
Ш Ш Ш 1,10,2,10 2 2,6,4,1 2,6,3,2 Ш Ш 2,6,3,5 2,10,2,6 2,6,3,7 Ш 2,6,4,9 2,10,2,10 2,6,3,10 3 Ш 3,2,10,2 3,2,6,3 3,7,9,3 3,2,6,4 3,2,6,5 3,2,10,5 3,10,2,6 Ш 3,7,9,8 Ш 3,10,2,10 4 Ш 4,9,3,2 4,1,10,2 Ш 4,9,8,4 4,9,3,5 4,1,10,5 4,1,2,6 4,9,3,7 Ш 4,9,8,9 4,1,2,10 4,9,3,10 5 Ш Ш Ш Ш Ш Ш Ш Ш Ш Ш 6 Ш 6,4,1,2 6,3,10,2 6,4,9,3 Ш 6,3,10,5 6,3,2,6 Ш 6,4,9,8 6,3,7,9 6,4,1,10 6,3,2,10 7
Ш 7,9,3,2 Ш 7,9,8,4 7,9,3,5 Ш 7,9,3,7 Ш 7,9,8,9 7,9,3,10 8 Ш 8,4,1,2 8,9,3,2 8,4,9,3 8,9,8,4 8,9,3,5 Ш 8,9,3,7 8,4,9,8 8,9,8,9 8,4,1,10 8,9,3,10 9 9,8,4,1 9,3,10,2 9,8,9,3 Ш 9,3,10,5 9,3,2,6 Ш 9,8,9,8 9,8,4,9 9,3,7,9 9,3,2,10 10 Ш 10,2,10,2 10,2,6,3 10,2,6,4 10,2,6,5 10,2,10,5 Ш Ш Ш Ш Ш И, наконец, построим искомую таблицу Г4. Данная таблица и будет ответом на поставленную задачу
о перечислении всех путей в ориентированном графе G, состоящих из 4 дуг. 10. Сформировать матрицу достижимости ориентированного графа G . Найти в ней строку, содержащую наименьшее количество нулей. Вершину, соответствующую этой строке, считать стартовой Найти кратчайшие пути от стартовой вершины до всех вершин ориентированного графа
G, достижимых из стартовой вершины. Матрицей достижимости графа G XG,PG, по определению, называется матрица, ТGn n, где nXG, элементы которой, определяются следующим образом 1, если xi,xj- путь в графе G ti,j 0, если xi,xj- путь в графе G. Тогда матрица достижимости выглядит таким образом 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1 1 5 0 0 0 0 0 0 0 0 0 0 6 1 1 1 1 1 1 1 1 1 1 7 1 1 1 1 1 1 1 1 1 1 8 1 1 1 1 1 1 1 1 1 1 9 1 1 1 1 1 1 1 1 1 1 10 1 1 1 1 1 1 1 1 1 1 Пусть вершина 1 будет стартовой. Найдм кратчайший путь от вершины 1 до вершины 2-10
Дадим ответ на поставленную задачу с помощью соответствующего алгоритма. Для этого, применяя алгоритм, добьмся того, чтобы метки всех вершин графа G стали постоянными. Ведь в том случае, когда метка постоянна, е значение есть ничто иное, как длина кратчайшего пути из заданной вершины в вершину с постоянной меткой. Итак, Шаг 1. Положим s10. Всем другим вершинам графа присвоим временную метку .
Параметр р1. Шаг 2. Образуем множество L1 2, 10 – множество вершин графа G, с временными метками, таких, что существует дуга из вершины 1 в эти вершины. Для каждой из вершин проверим выполняемость неравенства SxSp lp,x, x Lp Где через lp,x обозначена нагрузка дуги p,x. Если данное неравенство будет верно, то нужно присвоить метке sx sp lp,x и gxp.
Итак, для вершины 2 04 верно, значит s24 для 10 08 верно, значит s108 g21 g101 Шаг 3 Обозначим через Х множество вершин, имеющих на данный момент временные метки. X 2,3,4,5,6,7,8,9,10 Среди данных вершин найдм такую вершину, метка которой имеет минимальное значение. Такую метку будем считать постоянной. Метку s24 будем считать постоянной. Шаг 4. Положим р2, Шаг 22 L2 6,10 . Проверим выполняемость неравенства 6 413 верно s6 17 10 8204 неверно
gx 2 Шаг 32 Х 3,4,5,6,7,8,9,10 Наименьшую метку имеет вершина 10, значит s108-постоянная метка Шаг 42 Р 10, Шаг 23 L10 5 816верно, значит s524, g510 Шаг 33 X 3,4,5,6,7,8,9 Среди них наименьшую метку имеет вершина 6, s6 17. Теперь она постоянная. Шаг 43 Р6, Шаг 24 L6 3,5,4 3 1712 верно s329, g36 5 241714 неверно 4 217верно s419 g46 Шаг 34 X3,4,5,7,8,9,10 Наименьшей меткой обладает вершина 4.
Е считаем теперь постоянной. s419 . Шаг 44 Р4, Шаг 25 L4 9 1910верно s929, g94 Шаг 35 X 9,3,5,7,8 Наименьшую из всех меток имеет вершина 5. s524- постоянная. Шаг 45 Р5, Шаг 26 Но вершина 5 не имеет множества L5 Шаг 36 X 9,3,7,8 Наименьшие метки имеют вершины 3 и 9. Пусть это будет 3. s329. Шаг 46 P3, Шаг 27 L3 7, 299верно s738 g73
Шаг 37 X 9,7,8 Наименьшей меткой обладает вершина 9. s929.Е мы и будем считать постоянной. Шаг 47 Р9. Шаг 28 L9 8 2914верно, а значит s843 g89 Шаг 38 X 7,8 Наименьшей меткой обладает вершина 7, s7 38 Шаг 48 Р7 Шаг 29 На данном этапе множество вершин с временными метками, таких что существует дуга из вершины 7 в эти вершины, составить невозможно Шаг 39
X 8 Метку у вершины 8 считаем постоянной. S843 Теперь уже невозможно составить множество Х вершин с временной меткой, поэтому можно сказать, что все искомые пути уже найдены. Восстановим все найденные пути, используя метку g. В таком случае путь найдтся как 1, , ggz, gz, z Восстановим весь путь до вершины 8 из вершины11,2,6,4,9,8,l43 Поэтому можно записать уже ответ Ответ к заданию 10 1кратчайший путь из вершины 1 в вершину 2 есть путь 1,2,
l4 2кратчайший путь из вершины 1 в вершину 3 есть путь 1, 2, 6, 3, длина пути l29 3кратчайший путь из вершины 1 в вершину 4 есть путь 1,2,6,4, l19 4кратчайший путь из вершины 1 в вершину 5 есть путь 1,10,5, длиною l24 5кратчайший путь из вершины 1 в вершину 6 есть путь 1,2,6, длиною l17 6кратчайший путь из вершины 1 в вершину 7 есть путь 1,2,6,3,7, l38 7кратчайший путь из вершины 1 в вершину 8 есть путь 1,2,6,4,9,8, l43 8кратчайший путь из вершины 1 в вершину 9 есть путь 1,2,6,4,9.
Длина пути l29 9кратчайший путь из вершины 1 в вершину 10 есть путь 1,10, l8 HYPER13PAGE HYPER15 HYPER13PAGE HYPER1419HYPER15