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

Определение: Матрица смежности (соседства) вершин (p,q) – графа G=(V,E) с p вершинами есть квадратная симметричная матрица [p x p].

Замечание: Всякому графу соответствует его бинарная симметричная матрица смежности. Всякая бинарная симметричная квадратная матрица с нулевой диагональю соответствует некоторому графу.

Определение: Матрица инциденций (соответствий) (p,q) – графа G=(V,E) с p вершинами и q ребрами есть [p x q] матрица

Замечание: для всякого графа можно построить соответствующую ему бинарную матрицу инциденций.

Операции над графами

.
1) удаление вершины v из графа G приводит к подграфу G-v графа G без вершины v и принадлежащих вершине v ребер.
2) Удаление ребра e из графа G=(V,E) при сохранении вершин приводит к подграфу G-e=(V,E – {e})
3) Добавление ребра e = (u,v) к графу G=(V,E), содержащему вершины u,v, приводит к графу G+e=(V,E∪{e})

Матрицы, цепи, циклы, связность

Определение: Маршрут в графе G=(V,E) есть чередующаяся последовательности вершин и ребер v₀e₁v₁e₂v₂ …….v_n-1e_nv_n графа G, для которой каждое ребро принадлежит двум соседним вершинам. При этом v₀ — начало маршрута, v_n – конец, n – длина маршрута. Обозначается через [u,v] маршрут между вершинами u и v. Иногда маршрут отмечен только вершинами, иногда только ребрами. Маршрут нулевой длины состоит из единственной вершины.

Определение: Цепь в графе G есть маршрут без повторов ребер, возможны повторы вершин. Простая цепь в графе G есть цепь без повторов вершин, а следовательно и ребер.

Определение: Цикл в графе G, есть замкнутая цепь (в которой начало и конец одинаковы). Простой цикл не имеет повторов вершин (кроме начала и конца), а следовательно, и повторов ребер.

Замечание: цепь, простая цепь, цикл, простой цикл – есть некоторые подграфы в графе G.

Замечание: В Орграфе маршрут, цепь, цикл становятся ориентированными.

Определение: Контур есть ориентированный цикл.

Определение: Граф (Орграф) G связен, если любая пара его вершин u,v может быть соединена цепью (путем) от u к v. В противном случае, граф G несвязен. Компонента связности графа G есть наибольший по числу ребер связный подграф графа G.

Определение: Расстояние между двумя вершинами в графе есть длина кратчайшей цепи между этими вершинами.

Комментарии запрещены.