2 группа/

Материал из Saratov FIO Wiki
Перейти к: навигация, поиск

==Ориентированные графы==

Введение

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

1. Ориентированные графы

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

Пусть V — конечное непустое множество, V2 — его де­картов квадрат. Ориентированный граф (орграф)—это па­ра (V, А), где A  V2. Элементы множества V называют­ся вершинами орграфа G=(V, А), а элементы множества А — его дугами. Таким образом, дуга — это упорядочен­ная пара вершин. Множества вершин и дуг орграфа G обозначаются через VG и AG соответственно. Число |VG| называется порядком орграфа G и обозначается через |G|.

Если х = (u, v) — дуга, то вершины u и v называются ее концевыми вершинами, причем u называется началом дуги х, а. v — концом.
Дуга с совпадающими началом и концом, т. е. дуга вида (v, v), называется петлей. Можно определить ориентированные графы с несколькими дугами, имеющими общее начало и общий конец (мультиграфы). Такие дуги называются параллельными.

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

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

    Орграф называется сильным (или силъносвязным), если любые две его вершины достижимы друг из друга. Орграф называется односторонним (или односторонне-связным), если для любой пары его вершин по меньшей мере одна достижима из другой. Орграф называется слабым (слабосвязным, связным), если любые две его вершины соединены полупутем

Орграф является слабым тогда и только тогда, когда его основание — связный мультиграф. Орграф называется несвязным, если его основание — несвязный мультиграф. Ориентированный граф называется турниром, если его основание является полным графом. Этот класс графов получил свое название в связи со спортивными турнира­ми без ничьих, проводимыми по круговой системе. Резуль­таты встреч можно описать ориентированным графом, вершины которого соответствуют участникам соревнова­ний, а дуга (u, v) есть в орграфе, если участник u побе­дил участника v.

2. Описание алгоритма

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


Пусть дан граф G, - его матрица смежности. Элементы матрицы расстояний D можно вычислить при машинной реализации следующим образом: dij равно наименьшему из чисел n, для которых aijn > 0, где aijn - элемент матрицы An и равно бесконечности, если таких чисел нет. Пример. Дан граф G (рис. 7). Найти матрицу расстояний D.

Сначала найдем матрицу смежности A, элемент aij которой равен 1, если вершины xi и xj графа G смежны, и равен нулю в противном случае. В матрице D диагональные элементы будут равны нулю, так как расстояние между вершинами xi и xj, если i = j, считается равным нулю. Если элемент aij матрицы A равен 1, то соответствующий элемент dij матрицы D тоже будет равен 1. Недоопределенная матрица D изображена ниже. Умножим матрицу А саму на себя по правилу умножения матриц и найдем матрицу A2.

Balakovo PKTiM 953 GAMM.jpg

Способы задания графов:

Матрица инцидентности A. По вертикали указываются вершины, по горизонтали - ребра. aij=1 если вершина i инцидентна ребру j, в противном случае aij=0. Для орграфа aij=-1 если из вершины i исходит ребро j, aij=1 если в вершину i входит ребро j. Если ребро - петля, то aij=2. Список ребер. В первом столбце ребра, во втором вершины им инцидентные. Матрица смежности - квадратная симметричная матрица. По горизонтали и вертикали - все вершины. Dij= число ребер, соединяющее вершины i,j. Матрица Кирхгофа: bij=-1, если вершины i и j смежны, bij=0 если вершины i и j не смежны, bii=deg(i). Сумма элементов в каждой строке и каждом столбце матрицы Кирхгофа равна 0.

Заключение:

Главным итогом выполнения курсовой работы было создание программы определения сильных компонент ориентированного графа в соответствии с поставленной задачей и получение практических результатов работы программы. Созданная программа позволяет: - ввод размерности исходной матрицы смежности графа из файла; - формировать решение в соответствии с условием поставленной задачи; - вывод на экран исходного графа и полученных компонент. Созданная программа полностью удовлетворяет поставленной задаче, но при этом имеет ряд недостатков: - нет вывода на печать результатов расчета; - нет контроля правильности вводимых данных; - ограниченная размерность графа. Доработка указанных недостатков позволит сделать программу более универсальной и надежной.

Источник сайтов

[1] [2] [3] [4] [5]