Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Связность в графах.
S=(…, E0 , E1 , … En-1 , …) цепочка промежуточных ребер, связывающих вершины Е0=(х0, х1), Е1(х1, х2), E2=(х2, х3)… S={…(x0, x1), (x1, x2) … (xn-2, xn-1), (xn-1, xn), …} Полученное множество маршрутом на графе от х1 до хn S – множество, перечисленное множество вершин от х0 до хn, где х0 – начальное вершина, хn – конечная вершина все остальные промежуточные. Если xn = x0, то маршрут называется циклическим. Если все ребра маршрута различны, то маршрут называют цепью. Если в цепи промежуточная вершина не повторяется, то цепь называется простой. В зависимости от множества S говорят о маршруте конечном или бесконечном. Всего множества маршрут между двумя вершинами существуют минимальный маршрут удовлетворяющей аксиомам метрики. d(xi, xj) - расстояние 1. d(xi, xj)=0 2. d(xi, xj)= d(xj, xi) – рефл., симметр. 3. d(xi, xj) + d(xj, xn) ≥ d(xi, xk) 2-е вершины находящиеся в графе называются связными, если существуют маршрут S между 2-мя вершинами. S={(х0, х1), (х1, х2), …, (хn-1, xn)} Граф называется связным, если между двумя любыми вершинами графа можно указать маршрут связи. Т.к. установили адекватность между бинарным отношения и графами, то можно сказать, что отношение связности на графах является адекватным отношением эквивалентным в бинарных отношениях, т.е. по отношению связности графа можно разделить на пересечение подграфа. Внутри подграфов будет связь между вершинами. Между подграфами связь отсутствует. Т.к. графу свойственны явления непрерывности => ему должны быть свойственны новые операции. С помощью отношения (~) мы можем разбить граф на связные и не связные подграфы.
|