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

Пусть дан граф G = (V,E) = (p,q).

1. Перечисление: Сначала перечисляем элементы множества V:

, а потом – элементы множества Е: .

Пример 1: V= ,

E = ,

где , – кратные ребра, – петля, (V,E) – неориентированный граф.

2. Матрица смежности имеет p строк и p столбцов. На (i, j)-м месте

стоит число, которое означает, сколько ребер типа . В орграфе мы будем ставить число со знаком «+», если ориентирован от к и «–», если наоборот (от к ). Матрица является диагональной.

3. Матрица инцидентности. Инцидентность – геометрический термин, употребляемый для обозначения () отношения принадлежности между основными объектами. Дана матрица, которая содержит p столбцов и q строк. На пересечении i-й строки и j-го столбца стоит число 0 или 1, которое означает инцидентно ли данное ребро данной вершине.

4. С помощью диаграммы вершины графа изображаем точками на плоскости, а ребра – линиями, соединяющими соответствующие точки.