Способы задания графов

Способы задания графов

Здесь рассмотрены 4 основных способа задания графов. К каждому из них я постарался дать краткое, но понятное описание с примерами.

 

Геометрический способ

Это графическое изображение множества вершин (X) и множества связей (V) данного графа.

Неориентированный граф

 

Ориентированный граф

 

Алгебраический способ

Это указание множества вершин, множества дуг, множества рёбер и множества изолированных вершин данного графа.

Неориентированный граф

 

Ориентированный граф

 

Матрица смежности

Это квадратная матрица размером n на n, где n — кол-во вершин в графе.

Обозначается A (G).

Матрица заполняется построчно.

Далее «строка» — вершина, которая рассматривается в данной строке,

«столбец» — вершина, которая рассматривается в данном столбце.

Для неориентированного графа, в каждой ячейке ставится кол-во рёбер между «строкой» и «столбцом».

Неориентированный граф

Для ориентированного графа — кол-во дуг из «строки» в «столбец».

Ориентированный граф

Нули в главной диагонали (из левого верхнего угла в правый нижний) означают отсутствие петель.

 

Матрица инцидентности

Это прямоугольная матрица n на m, где n — кол-во вершин в данном графе, m — кол-во связей.

Обозначается B (G).

Матрица заполняется по столбцам.

Для неориентированного графа, в каждой ячейке ставится: 1 — если вершина инцидентна этому ребру (присоединена к нему), 0 — если вершина не инцидентна данному ребру.

Неориентированный граф

Для ориентированного графа: 1 — если вершина является началом данной дуги, -1 — если вершина является концом, 0 — если вершина не инцидентна данной дуге.

Ориентированный граф

Как вы наверное заметили, в одном столбце всегда два числа, отличных от нуля, т.к. любая связь всегда имеет одно начало и один конец, ни больше ни меньше.

TEXT.RU - 100.00%

Поделиться ссылкой:

Добавить комментарий

Зарегистрируйтесь или Войдите, чтобы оставить комментарий.

Системное сообщение