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

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

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


где aij:
— 1, если вершины Vi,Vj — соседние
— 0, в противном случае

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

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


где Bij:
1, если вершина Vi∈ ребру ej
0, в противном случае

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

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

.
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) есть чередующаяся последовательности вершин и ребер v0e1v1e2v2 …….vn-1envn графа G, для которой каждое ребро принадлежит двум соседним вершинам. При этом v0 — начало маршрута, vn – конец, n – длина маршрута. Обозначается через [u,v] маршрут между вершинами u и v. Иногда маршрут отмечен только вершинами, иногда только ребрами. Маршрут нулевой длины состоит из единственной вершины.

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

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

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

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

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

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

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


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





Статистика

Рейтинг@Mail.ru