- •Типы графов
- •Маршруты и связность
- •Степени
- •Задача Рамсея
- •Экстремальные графы
- •Графы пересечений
- •Операции над графами
- •Графы блоков и точек сочленения
- •Точки сочленения, мосты и блоки
- •Деревья
- •Описание деревьев
- •Центры и центроиды
- •Деревья блоков и точек сочленения
- •Независимые циклы и коциклы
- •Матроиды
- •Обходы графов
- •Эйлеровы графы
- •Гамильтоновы графы
- •Реберные графы
- •Некоторые свойства реберных графов
- •Характеризация реберных графов
- •Специальные реберные графы
- •Реберные графы и обходы
- •Тотальные графы
- •Раскраски
- •Хроматическое число
- •Теорема о пяти красках
- •Гипотеза четырех красок
- •Однозначно раскрашиваемые графы
- •Критические графы
- •Гомоморфизмы
- •Хроматический многочлен
- •Матрицы
- •Матрица смежностей
- •Матрица инциденций
- •Матрица циклов
- •Обзор дополнительных свойств матроидов
- •Связность
- •Связность и реберная связность
- •Орграфы
- •Орграфы и соединимость
- •Ориентированная двойственность и бесконтурные орграфы
- •Орграфы и матрицы
- •Турниры
- •Обзор по проблеме востановления турниров
- •Волновой алгоритм
- •Алгоритм Дейкстры
- •Алгоритм Флойда
- •Алгоритм Йена
- •Алгоритм Краскала
Орграфы и матрицы
Матрицей смежностейA (D)орграфаD называется (рр)-матрица
у которой aij = 1, еслиviuj- дуга oprpaфа D, и аij=0 в противном случае.
Легко проверить, что суммы элементов по строкам матрицы A (D) равны полустепеням исхода вершин орграфа D, а суммы элементов по столбцам — полустепеням захода.
Как и в случае графов, степени матрицы смежностей А орграфа дают полную информацию о числе маршрутов, идущих из одной вершины в другую.
Теорема (i, j)-й элемент аij матрицы Аn равен числу маршрутов длины n, идущих из вершины vi в вершину vj.
Упомянем здесь вкратце еще о трех матрицах, связанных с орграфом D -
о матрице достижимостей, матрице расстояний и матрице обходов. В матрице достижимостей R элемент rij равен 1, если вершина viдостижима изvj, и равен 0 в противном случае. Вматрице расстояний (i, j)-й элемент равен расстоянию из вершины viв вершину vj, если же из vi в vj нет путей, то соответствующий элемент полагаем равным бесконечности. Вматрице обходов(i, j)-й элемент равен длине наиболее длинного пути из vi в vj , а если таких путей нет, то опять-таки полагаем этот элемент равным бесконечности.
Следствие(а).Элементы матриц достижимостей и расстояний связаны со степенями матрицы А следующими соотношениями:
1) rij=1 и dij=0 для всех i;
2) rij = 1 тогда и только тогда, когда aijn>0 для некоторого n;
3) d(vi, vj) равно наименьшему из чисел n, для которых аijn> 0, и , если таких чисел нет.
Эффективных методов для нахождения элементов матрицы обходов не существует. Эта проблема тесно связана с некоторыми другими давно поставленными алгоритмическими проблемами теории графов, такими, как нахождение остовных циклов и контуров, а также решение задачи о коммивояжере.
Следствие(б).Пусть vi- вершина орграфа D. Сильные компоненты орграфа D, содержащие vi, определяются единичными элементами i-й строки (или i-го столбца) матрицы RRT.
Формула для числа остовных входящих деревьев данного орграфа была найдена Боттом и Мейберри, а доказана Таттом. Чтобы сформулировать этот результат, известный как матричная теорема о деревьях для орграфов, введем еще матрицы, связанные с D. Обозначим через Mod матрицу, полученную из -А заменой i-ro элемента главной диагонали на od (vi). Двойственным образом определим матрицу Мid.
Теорема.Для каждого помеченного орграфа D алгебраическое дополнение любого элемента i-й строки матрицы Мid равно числу остовных входящих деревьев, у которых вершина vi является стоком.
Теорема.Для каждого помеченного орграфа D алгебраическое дополнение любого элемента j-го столбца матрицы Mid равно числу остовных выходящих деревьев, у которых вершина vj является источником.
Следующий алгоритм (Харари ) иногда упрощает вычисление собственных значений матрицы М, а также нахождение матрицы, обратной к М (если она существует).
1. Образовать орграф D, связанный с М.
2. Определить сильные компоненты орграфа D.
3. Образовать конденсацию D*.
4. Упорядочить сильные компоненты так, чтобы матрица смежностей орграфа D* стала верхней треугольной.
5. Используя сильные компоненты, переупорядочить вершины орграфа D так, чтобы привести его матрицу смежностей А к верхнему треугольному виду.
6. Заменить каждый единичный элемент матрицы А соответствующим ему элементом матрицы М.
Собственные значения матрицы М являются собственными значениями диагональных блоков новой матрицы, а матрицу, обратную к М, можно найти, обращая эти диагональные блоки.
Если М — разреженная матрица (или, скорее, матриц с таким расположением нулевых элементов, что в графе имеется несколько сильных компонент), то указанный алгоритм может быть весьма эффективным. Вариант этого алгоритма (иногда более эффективный, но также и более сложный) для двудольных графов был дан Далмеджем и Мендельсоном.