ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

Графы предназначены для наглядного представления информации о связях между объектами: схема автомобильных дорог, схема линий метро, схема переходов между состояниями компьютера и т.д.

Определение. Граф Г=(V, R) – фигура из множества точек – вершин графа и множества отрезков, или дуг – ребер графа, соединяющих его некоторые вершины.

Обозначение. - ребро, соединяющее вершины и (если это ребро существует и единственно). Если вершины и соединены несколькими ребрами, то для того, чтобы различать их, на них ставят фиктивные вершины:

Подграф Г’=(V’, R’) графа Г – это некоторая часть графа Г: V’ V, R’ R.

Как хранить граф в компьютере?

Определение. Матрица смежности :

Очевидно, что А – симметричная матрица, то есть .

Замечание.Если не единственное ребро графа, то = число ребер, соединяющих вершины и (это мы использовать не будем).