Связность в графах.

S=(…, E₀ , E₁ , … E_n-1 , …) цепочка промежуточных ребер, связывающих вершины Е₀=(х₀,х₁), Е₁(х₁,х₂), E₂=(х₂,х₃)…
Если теперь взять последовательность ребер, то получим:

S={…(x₀,x₁), (x₁,x₂) … (x_n-2, x_n-1), (x_n-1, x_n), …}

Полученное множество маршрутом на графе от х₁ до х_n

S – множество, перечисленное множество вершин от х₀ до х_n, где х₀ – начальное вершина, х_n – конечная вершина все остальные промежуточные.

Если x_n = x₀, то маршрут называется циклическим. Если все ребра маршрута различны, то маршрут называют цепью. Если в цепи промежуточная вершина не повторяется, то цепь называется простой. В зависимости от множества S говорят о маршруте конечном или бесконечном.

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

d(x_i, x_j) - расстояние

1. d(x_i, x_j)=0

2. d(x_i, x_j)= d(x_j, x_i) – рефл., симметр.

3. d(x_i, x_j) + d(x_j, x_n) ≥ d(x_i, x_k)

2-е вершины находящиеся в графе называются связными, если существуют маршрут S между 2-мя вершинами.

S={(х₀, х₁), (х₁, х₂), …, (х_n-1, x_n)}

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

Т.к. установили адекватность между бинарным отношения и графами, то можно сказать, что отношение связности на графах является адекватным отношением эквивалентным в бинарных отношениях, т.е. по отношению связности графа можно разделить на пересечение подграфа. Внутри подграфов будет связь между вершинами. Между подграфами связь отсутствует.

Т.к. графу свойственны явления непрерывности => ему должны быть свойственны новые операции.

С помощью отношения (~) мы можем разбить граф на связные и не связные подграфы.

Дата добавления: 2015-09-01