Представление графов в компьютере

Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скорости выполнения операций над графами. Преставление выбирается исходя из потребностей конкретной задачи. В подавляющем большинстве случаев граф задается матрицей. Чаще всего графы представляют либо матрицей смежности, либо матрицей инциденций.

Определение 1.11. Матрица смежности вершин орграфа , содержащего вершин, − это квадратная матрица у которой строки и столбцы матрицы соответствуют вершинам орграфа. Элементы матрицы равны числу дуг, направленных из -ой вершины в -ую. Если орграф состоит из однократных дуг, то элементы матрицы равны либо , либо .

Матрицей смежности вершин неориентированного графа , содержащего вершин, называют квадратную матрицу у которой строки и столбцы матрицы соответствуют вершинам неориентированного графа. Элементы матрицы равны числу ребер, направленных из -ой вершины в -ую. В случае неориентированного графа ему вместе с ребром принадлежит и ребро , поэтому матрица смежности вершин будет симметрична относительно главной диагонали.

Определение 1.12. Матрица смежности дуг орграфа − это квадратная матрица у которой строки и столбцы матрицы соответствуют дугам орграфа. Элементы матрицы равны , если дуга непосредственно предшествует дуге и в остальных случаях.

Матрицей смежности ребер неориентированного графа является матрица у которой строки и столбцы матрицы соответствуют ребрам графа. Элементы матрицы равны , если ребра и имеют общую вершину и в остальных случаях.

Определение 1.13. Матрицей инциденций (инцидентности) неориентированного помеченного графа с вершинами и ребрами называется матрица , строки которой соответствуют вершинам, а столбцы – ребрам. Элементы матрицы инциденций неориентированного графа равны , если вершина инцидентна ребру , и в противном случае.

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

Если каждому ребру графа приписано некоторое положительное число, то такое число называется весом, а сам граф называется взвешенным графом. Простой взвешенный граф (сеть) может быть представлен также своей матрицей весов , где – вес ребра, соединяющего вершины и . Весы несуществующих ребер (дуг) полагают равными нулю или бесконечности в зависимости от приложений.