С помощью матрицы смежности

Матрица смежности – квадратная матрица ||δ_ij|| строкам и столбцам которой соответствуют вершины графа.

Для неориентированного графа δ_ij равна количеству ребер, инцидентных i и j вершине.

Для ориентированного графа δ_ij равна количеству ребер с началом в i – вершине и концом в j – вершине.

Для неориентированного графа: Для ориентированного графа:

Таблица 19 Матрица смежности Таблица 20 Матрица смежности

для неориентированного графа для ориентированного графа

Матрица для неориентированного графа симметрична относительно главной диагонали.

Пусть G – неориентированный граф. Маршрутом G называется такая конечная или бесконечная последовательность ребер (е₁, е₂,…,е_n), что каждые два соседних ребра

е_i-1, е_i имеют общую инцидентную вершину.

Пусть маршрут М, состоящий из (е₁, е₂,…,е_n) ребер, имеет начало V₀ и конец V_n.

Если V₀ =V_n (начало совпадает с вершиной), то такой маршрут называется циклическим.

Маршрут М называется цепью, если каждое ребро встречается в нем не более 1 раза.

Циклический маршрут называется циклом, если он является цепью.

ПРИМЕР:

Рис.23. Неориентированный граф

Маршрут: М = {VI, IV, III, II, VI, I}

Циклический маршрут: M = {I, VI, IV, III, II, VI, I}

Цепь: M = {IV, III, II, VI, I}

Цикл: M = {IV, III, II}

Вершины V` и V``, принадлежащие графу G, называются связанными, если существует маршрут М с началом V` и концом V``.

Граф G называется связанным, если все его вершины связаны между собой.

Рис.24. Связанный граф

Несвязанный граф:

Рис.25. Несвязанный граф

Неориентированным деревом называется связанный неориентированный граф без циклов.

Рис.26. Дерево

Несвязанный, неориентированный граф без циклов называется лесом.

Рис.27. Лес

Дата добавления: 2015-06-27