Матрицы графов

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

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

Из определения матрицы смежностей вершин неориентированного графа и ее основных свойств следуют некоторые особенности соответствия между графом G(X, E) и его матрицей A(G). На рис. 1 указана некоторая нумерация вершин графа; расположенная рядом матрица соответствует именно этой нумерации. Если же в графе G(X, E), приведенном на этом рисунке, использовать другую нумерацию вершин (например, сдвинув ее относительно вершин по часовой стрелке), то это приведет к тому, что в матрице A(G) произойдет перестановка отдельных строк и столбцов.

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