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

Существует много способов представить граф, назовем только самые распространенные.

1. Перечисление элементов. Исходя из определения, для того, чтобы задать граф, достаточно перечислить его вершины и ребра (т.е. пары вершин).

2. Изображение. Если граф невелик, его можно нарисовать. В неориентированном графе ребра изображаются линиями, в ориентированном – стрелками.

3. Матрица смежности. Пусть G – граф с n вершинами, пронумерованными числами от 1 до n. Матрица смежности – это таблица с n строками и n столбцами, в которой элемент, стоящий на пересечении строки с номером i и столбца с номером j, равен 1, если вершины с номерами i и j смежны, и 0, если они не смежны.

4. Матрица инцидентности. Пусть G – граф, вершины которого пронумерованы числами от 1 до n, а ребра – числами от 1 до m. В матрице инцидентности строки соответствуют вершинам, а столбцы – ребрам. На пересечении строки с номером i и столбца с номером j стоит 1, если вершина с номерами i инцидентна ребру с номером j смежны, и 0 в противном случае.

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