zhChinese    enEnglish
  ПМ-ПУ  » Образование  » Программы курсов » Матричные методы теории графов

Матричные методы теории графов

Разработчики: к.ф.-м.н., доц. Хитров Г.М.

I. Дополнительные (по отношению к читаемым курсам) сведения из алгебры и теории матриц.

  1. Линейные отображения и операторы и их матрицы. Ядро и образ линейного отображения (оператора). Примеры вычисления базиса ядра над полем по модулю два.
  2. Разложимые и неразложимые неотрицательные матрицы. Сильная и слабая разложимость матрицы. Критерий разложимости (неразложимости) матриц.
  3. Примитивные и импримитивные матрицы. Критерий импримитивности матриц.
  4. Формула Бине-Коши.
  5. Критерий регулярности Адамара и его обобщения.
  6. Характеристический многочлен матрицы и выражение его коэффициентов через главные миноры матрицы.
  7. Метод Фаддеева одновременного вычисления коэффициентов характеристического многочлена и присоединенной матрицы.
  8. Теорема об алгебраических дополнениях элементов матрицы с нулевыми строчными суммами.
  9. Сопровождающая матрица для многочлена ([1, стр. 151]) Нормальная форма многочленной (в частности - характеристической) матрицы. Пример вычисления нормальной формы характеристической (0,1)-матрицы над полем по модулю два.

II. Матричные определения графа и основных графовых понятий.

  1. Определение графа (геометрическое) и построение квадратной (0,1)-матрицы смежности графа с пронумерованными вершинами. Изменение нумерации вершин графа и соответствующее изменение матрицы смежности графа. Преобразование перестановочного подобия (0,1)-матриц. Определение графа как класса квадратных перестановочно подобных между собой матриц.
  2. Определение пути в графе и выражение его через произведение элементов матрицы смежности. Определение длины пути. Интерпретация элемента k-ой степени матрицы смежности, расположенного на месте (i,j), как числа путей длины k, идущих из i-ой вершины в j-ую.
  3. Определение расстояния между вершинами в графе. Построение индикаторной матрицы для k-ой степени матрицы смежности. Использование булевой арифметики для её построения. Матрица расстояний графа.
  4. Транзитивные графы и транзитивное замыкание графа. Транзитивные (0,1)-матрицы и транзитивное замыкание (0,1)-матрицы. Использование булевой арифметики для построения транзитивного замыкания матрицы.
  5. Определение типов связности графа. Использование транзитивного замыкания матрицы смежности графа для определения типов связности графа.
  6. Сильная связность графа и построение компонент связности.
  7. Понятие о нормальных формах матрицы смежности графа.
  8. Подграфы. Определение подграфов через подматрицы матрицы смежности. Остовные подграфы. Определение остовного подграфа через произведение неповторяющихся ненулевых элементов матрицы смежности.
  9. Деревья и ориентированные деревья.
  10. Ориентированные деревья, как разновидности остовных подграфов. Матричные теоремы о числе входящих и числе выходящих из вершины деревьев.
  11. Инварианты графа. Характеристический многочлен матрицы смежности графа и его коэффициенты, как инварианты графа. Определитель и перманент матрицы смежности графа и их графовая интерпретация. Графовая интерпретация коэффициентов характеристического полинома.
  12. Матричные инварианты графа. Разнообразие графа.
  13. Изоморфизм графов как перестановочное подобие их матриц смежности. Использование матричных инвариантов для построения алгоритмов проверки графов на их изоморфизм.
  14. Определение графа, как оператора в векторном пространстве над полем по модулю два. Характеристический многочлен оператора-графа и нормальная форма характеристической матрицы оператора (всё над полем по модулю два), как основа для классификации графов (разбиения множества графов на непересекающиеся подмножества).

III. Обыкновенные графы (важный частный случай графов) и особенности их матричного представления.

  1. Геометрическое определение обыкновенного графа, определение инцидентности между вершинами и ребрами. Матрица инциденций. Изменение матрицы инциденций при изменении нумерации вершин и ребер (перестановочно эквивалентное преобразование матриц).
  2. Связь матрицы инциденций с матрицей смежности графа.
  3. Изоморфизм обыкновенных графов.
  4. Обыкновенный граф как линейное отображение пространства ребер в пространство вершин, когда каждое ребро отображается в инцидентную ему пару вершин. Оба пространства являются пространствами (0,1)-столбцов соответствующих размерностей, т.е. пространствами над полем по модулю 2. Матрица линейного отображения в базисах столбцов с одной единицей и остальными нулями является матрицей инциденций.
  5. Ядро линейного отображения из 4 как пространство циклов.
  6. Линейное отображение пространства вершин в пространство ребер, когда каждая вершина отображается в линейную комбинацию инцидентных ему ребер. Матрица этого отображения в базисах, как и в 4, является транспонированной к матрице инциденций. Связь между элементами ядра этого отображения и компонентами связности графа.
  7. Теоретические основы разбиения обыкновенного графа на компоненты связности. Алгоритм разбиения графа на компоненты связности.
  8. Разбиение множества вершин на непересекающиеся множества несмежных между собой вершин (вершинная раскраска графов). Алгоритмы вершинной и реберной раскраски графов.
  9. Точки сочленения и мосты. Блоки. Разбиения графа на блоки. Граф блоков.
  10. Деревья. Матричная теорема о деревьях.

IV. Специальные (дополнительные) вопросы матричной теории графов.

  1. Сети. Определение сети как "взвешенного" графа. Примеры сетей (из экономики - матрица обмена; из теории экспертных оценок - матрица парных экспертных сравнений).
  2. Плоские графы и планарность. Критерии планарности.
  3. Рисование графов на плоскости. Укладка графа. Пример укладки графа с использованием простейшего функционала.

Литература

  1. Гантмахер Ф.Р. Теория матриц. Изд-во "Наука", М., 1967. 578 с.
  2. Харари Ф. Теория графов. Изд-во "Мир", М., 1973. 302 с.
  3. ГрафоMann