Орграфы, теория и применение
Информация - Математика и статистика
Другие материалы по предмету Математика и статистика
?сло ребер, c - чсло компонент связности графа. Коциклический ранг (или коранг) ?*=n-c.
Теорема. Число ребер неографа, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно цикломатическому числу графа.
Неограф G является лесом тогда и только тогда, когда ?(G)=0. Неограф G имеет единственный цикл тогда и только тогда, когда ?(G)=1. Остов неографа имеет ?* ребер. Ребра графа, не входящие в остов, называются хордами. Цикл, получающийся при добавлении к остову графа его хорды, называется фундаментальным относительно этой хорды.
Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Очевидно, что для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины u и каждой другой вершины v существовал (u, v)- маршрут.
Теорема. Граф G=(V,E) связен тогда и только тогда, когда множество го вершин нельзя разбить на два непустых подмножества V1 и V2 так, чтобы бе граничные точки каждого ребра находились в одном и том же множестве. Всякий максимальный связный подграф графа G называется связной компонентой (или компонентой) графа G. Слово "масимальный" оначает максимальный относительно включения, т.е. не содержащийся в связном подграфе с большим числом элементов. Множество вершин связной компоненты называется областью связности. Для ориентированного графа вводится понятие ориентированного маршрута это последовательность вида (1), в которой ei=(vi,vi+1). Аналогом цепи в этой итуации служить путь (ориентированная цепь). Аналогом цикла служит контур ориентированный цикл).
Орграф называется сильносвязным, если любые две его вершины достижимы руг из друга. Орграф называется одностороннесвязным, если для любой пары его вершин по меньшей мере одна достижима из другой. Орграф называется слабосвязным, если любые две вершины его основания соединены маршрутом. Орграф называется несвязным, если его основание несвязный псевдограф.
Теорема. Орграф является сильносвязным тогда и только тогда, когда в нем есть основной циклический маршрут.
Необходимость. Пусть G сильносвязный орграф и T=(v0, x1, v1, ..., xn, v0) его циклический маршрут, проходящий через максимально возможное число вершин. Если этот маршрут не является остовным, то возьмем вне его вершину v. Так как G сильносвязный орграф, то существуют маршруты T1=(v0, y1, ..., v), T2=(v, z1, ..., v0). Но тогда циклический маршрут T=(v0, x1, v1, ..., xn, v0, y1, ..., v, z1, ..., v0) содержит большее число вершин, чем T, что противоречит выбору маршрута T. Следовательно, T остовной маршрут.
Достаточность. Пусть u и v две произвольные вершины орграфа G, а T=(v0, x, ..., v, y, ..., u, z, ..., v0) циклический маршрут. Тогда u достижима из v с помощью маршрута (v, y, ..., u) части маршрута T, а v из u с помощью маршрута (u, z, ..., v0, x, ..., v).3
Теорема. Орграф является одностороннесвязным тогда и только тогда, когда в нем есть остовной маршрут.
Теорема. Орграф является слабосвязным тогда и только тогда, когда в его основание есть связный псевдограф.
Сильносвязной компонентой орграфа называется его максимальный относительно включения сильносвязный подграф.
Матричное представление графов
Орграфы и матрицы. Матрицей сложностей A (D) орграфа D называется (рхр)-матрица \\аи\\> У которой ai}=\, если vfl, дуга орграфа D, и atj~Q в противном случае. Сумма по столбцу легко проверить, что суммы элементов по строкам матрицы A (D) равны полустепеням исхода вершин орграфа D, а суммы элементов по столбцам полустепеням захода. Как и в случае графов, степени матрицы смежностей. А орграфа дают полную информацию о числе маршрутов, идущих из одной вершины в другую. Есть еще три матрицы, связанные с орграфом D матрица достижимостей, матрица расстояний и матрица обходов. Матрицу достижимостей орграфа можно использовать для нахождения его сильных компонент. Формула для числа остовных входящих деревьев данного орграфа была найдена BOTTOM и Мейберри, а доказана Таттом. Чтобы сформулировать этот результат, известный как матричная теорема о деревьях для орграфов, введем еще матрицы, связанные с D. Для каждого помеченного орграфа D алгебраическое дополнение любого элемента 1-й строки матрицы Mod равно числу остовных входящих деревьев, у которых вершина vt является стоком. Для каждого помеченного орграфа D алгебраическое дополнение любого элемента j-го столбца матрицы Mid равно числу остовных выходящих деревьев, у которых вершина Vj является источником. Эйлеров контур в орграфе D это замкнутый остовный маршрут, в котором каждая дуга орграфа D встречается по одному разу. Орграф называется эйлеровым, если в нем есть эйлеров контур. Для графов, можно легко показать, что слабый орграф D эйлеров тогда и только тогда, когда у каждой его вершины полустепень захода равна полустепени исхода. Сформулируем теперь теорему, в которой дается формула для числа эйлеровых контуров в эйлеровых орграфах. Эту теорему можно доказать очень изящно с помощью матричной теоремы о деревьях для орграфов; В эйлеровом орграфе число эйлеровых контуров равно с \\ (d,-1)! Заметим, что для эйлерова орграфа МоА=М\А и все суммы и по строкам, и по столбцам равны нулю, так что все алгебраические дополнения равны между собой. Первый орграф с тремя вершинами называется транзитивной тройкой, второй циклической тройкой.
Орграф называется строго слабым, если он слабый и не односторонний; строго односторонним, если он односторонний и не сильный. Пусть С0 класс всех несвязных орграфов, GI класс всех строго слабых орграфов, С2 класс всех строго односторонних ор