Части графа

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

Граф G’=(V’, Е’) называется его подграфом, если он получен из исходного путем удалением части вершин вместе с инцидентными им ребрами.

Например, если из графа представленного на рис.6 удалить вершины 3 и 5, то получим граф

Всего из одного графа можно получить 2ⁿ подграфов.

Исходный граф по отношению к подграфу называется надграфом.

Маршрутом между вершинами v и w в графе G=(V, Е) называется последовательность ребер вида (v,x₁), (x₁,x₂), (x₂,x₃),…, (x_n-1,x_n), (x_n,w).

Например,

Рис. 7 Рис.8.

(1,2), (2,3)-маршрут из первой вершины в третью.

Маршрут, у которого начальная вершина совпадает с конечной называется циклом. Например, на рис.8 (1,2), (2,3), (3,4), (4,1).

Вершина v называется достижимой из вершины w, если существует маршрут из w в v. Вершины v и w взаимнодостижимы если существует маршрут из v в w и маршрут из w в v. Для неориентированных графов достижимость вершин влечет взаимодостижимость.

Вершина графа для которой не существует достижимых вершин и которая не достижима из других вершин называется изолированной.

Очевидно, что вершина изолирована тогда и только тогда когда у нее нет инцедентных ребер.

Пример.

Вершина 5 – изолированная вершина.

Дата добавления: 2014-01-20