Лекция: Графы. Виды и алгоритмы обработки

Способы представления графов

• Граф, как и большинство других математических объектов, может быть представлен на компьютере (сохранен в его памяти). Существуют несколько способов его интерпретации, вот наиболее известные из них:
• матрица смежности;
• матрица инцидентности;
• список смежности;
• список ребер.

G – граф

• G – граф
• V – вершины
• E – ребра(дуги, веса)
• n = |V| – число вершин
• m = |E| – число рёбер.
• Матрицей смежности графа G называют квадратную матрицу A порядка n, в которой:
• ДЛЯ ОРИЕНТИРОВАННОГО И НЕОРИЕНТИРОВАННОГО ГРАФА:
• Aij = 1 если вершины i и j соединены ребром (дугой)
• Aij = 0 если вершины i и j не имеют общее ребро

Матрицей инцидентности графа G называют матрицу B, состоящую из n строк(вершины) и m столбцов(ребра), в которой:

• Матрицей инцидентности графа G называют матрицу B, состоящую из n строк(вершины) и m столбцов(ребра), в которой:
• ДЛЯ НЕОРИЕНТИРОВАННОГО ГРАФА:
• Bij = 1 если вершина i инцидентна ребру j
• Bij = 0 если вершина i не инцидентна ребру j
• ДЛЯ ОРИЕНТИРОВАННОГО ГРАФА:
• Bij = 1 если вершина i является началом дуги j
• Bij = 0 если вершина i не инцидентна дуге j
• Bij = -1 если вершина i является концом дуги j
• Список смежности (смежных вершин) (adjacency list) – это массив A[n], каждый элемент A[i] которого содержит список узлов смежных с вершиной i.
• Список ребер (edges list) – это линейный список ребер смежных узлов.