Матричные методы теории графов
Разработчики: к.ф.-м.н., доц. Хитров Г.М.
I. Дополнительные (по отношению к читаемым курсам) сведения из алгебры и теории матриц.
- Линейные отображения и операторы и их матрицы. Ядро и образ линейного отображения (оператора). Примеры вычисления базиса ядра над полем по модулю два.
- Разложимые и неразложимые неотрицательные матрицы. Сильная и слабая разложимость матрицы. Критерий разложимости (неразложимости) матриц.
- Примитивные и импримитивные матрицы. Критерий импримитивности матриц.
- Формула Бине-Коши.
- Критерий регулярности Адамара и его обобщения.
- Характеристический многочлен матрицы и выражение его коэффициентов через главные миноры матрицы.
- Метод Фаддеева одновременного вычисления коэффициентов характеристического многочлена и присоединенной матрицы.
- Теорема об алгебраических дополнениях элементов матрицы с нулевыми строчными суммами.
- Сопровождающая матрица для многочлена ([1, стр. 151]) Нормальная форма многочленной (в частности - характеристической) матрицы. Пример вычисления нормальной формы характеристической (0,1)-матрицы над полем по модулю два.
II. Матричные определения графа и основных графовых понятий.
- Определение графа (геометрическое) и построение квадратной (0,1)-матрицы смежности графа с пронумерованными вершинами. Изменение нумерации вершин графа и соответствующее изменение матрицы смежности графа. Преобразование перестановочного подобия (0,1)-матриц. Определение графа как класса квадратных перестановочно подобных между собой матриц.
- Определение пути в графе и выражение его через произведение элементов матрицы смежности. Определение длины пути. Интерпретация элемента k-ой степени матрицы смежности, расположенного на месте (i,j), как числа путей длины k, идущих из i-ой вершины в j-ую.
- Определение расстояния между вершинами в графе. Построение индикаторной матрицы для k-ой степени матрицы смежности. Использование булевой арифметики для её построения. Матрица расстояний графа.
- Транзитивные графы и транзитивное замыкание графа. Транзитивные (0,1)-матрицы и транзитивное замыкание (0,1)-матрицы. Использование булевой арифметики для построения транзитивного замыкания матрицы.
- Определение типов связности графа. Использование транзитивного замыкания матрицы смежности графа для определения типов связности графа.
- Сильная связность графа и построение компонент связности.
- Понятие о нормальных формах матрицы смежности графа.
- Подграфы. Определение подграфов через подматрицы матрицы смежности. Остовные подграфы. Определение остовного подграфа через произведение неповторяющихся ненулевых элементов матрицы смежности.
- Деревья и ориентированные деревья.
- Ориентированные деревья, как разновидности остовных подграфов. Матричные теоремы о числе входящих и числе выходящих из вершины деревьев.
- Инварианты графа. Характеристический многочлен матрицы смежности графа и его коэффициенты, как инварианты графа. Определитель и перманент матрицы смежности графа и их графовая интерпретация. Графовая интерпретация коэффициентов характеристического полинома.
- Матричные инварианты графа. Разнообразие графа.
- Изоморфизм графов как перестановочное подобие их матриц смежности. Использование матричных инвариантов для построения алгоритмов проверки графов на их изоморфизм.
- Определение графа, как оператора в векторном пространстве над полем по модулю два. Характеристический многочлен оператора-графа и нормальная форма характеристической матрицы оператора (всё над полем по модулю два), как основа для классификации графов (разбиения множества графов на непересекающиеся подмножества).
III. Обыкновенные графы (важный частный случай графов) и особенности их матричного представления.
- Геометрическое определение обыкновенного графа, определение инцидентности между вершинами и ребрами. Матрица инциденций. Изменение матрицы инциденций при изменении нумерации вершин и ребер (перестановочно эквивалентное преобразование матриц).
- Связь матрицы инциденций с матрицей смежности графа.
- Изоморфизм обыкновенных графов.
- Обыкновенный граф как линейное отображение пространства ребер в пространство вершин, когда каждое ребро отображается в инцидентную ему пару вершин. Оба пространства являются пространствами (0,1)-столбцов соответствующих размерностей, т.е. пространствами над полем по модулю 2. Матрица линейного отображения в базисах столбцов с одной единицей и остальными нулями является матрицей инциденций.
- Ядро линейного отображения из 4 как пространство циклов.
- Линейное отображение пространства вершин в пространство ребер, когда каждая вершина отображается в линейную комбинацию инцидентных ему ребер. Матрица этого отображения в базисах, как и в 4, является транспонированной к матрице инциденций. Связь между элементами ядра этого отображения и компонентами связности графа.
- Теоретические основы разбиения обыкновенного графа на компоненты связности. Алгоритм разбиения графа на компоненты связности.
- Разбиение множества вершин на непересекающиеся множества несмежных между собой вершин (вершинная раскраска графов). Алгоритмы вершинной и реберной раскраски графов.
- Точки сочленения и мосты. Блоки. Разбиения графа на блоки. Граф блоков.
- Деревья. Матричная теорема о деревьях.
IV. Специальные (дополнительные) вопросы матричной теории графов.
- Сети. Определение сети как "взвешенного" графа. Примеры сетей (из экономики - матрица обмена; из теории экспертных оценок - матрица парных экспертных сравнений).
- Плоские графы и планарность. Критерии планарности.
- Рисование графов на плоскости. Укладка графа. Пример укладки графа с использованием простейшего функционала.
Литература
- Гантмахер Ф.Р. Теория матриц. Изд-во "Наука", М., 1967. 578 с.
- Харари Ф. Теория графов. Изд-во "Мир", М., 1973. 302 с.
- ГрафоMann