АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Связность

Читайте также:
  1. Разорванность мышления, бессвязность, резонерство, формализм, патологическая обстоятельность.
  2. Связность объектов
  3. Синтаксическая связность

 

Пусть G - неориентированный граф. Маршрутом в G называется такая конечная или бесконечная последовательность ребер

, (1)

что каждые два соседних ребра и - имеют общую концевую точку. Та­ким образом, можно записать

. (2)

Одно и то же ребро а может встретиться в маршруте несколько раз. Ес­ли в (1) нет ребер, предшествующих , то называется начальной вер­шиной S, а если нет ребер, следующих за , то называется конечной вершиной S. Любая вершина в (2), принадлежащая двум соседним реб­рам и , называется внутренней, или промежуточной, вершиной. Маршрут называется нетривиальным, если он содержит хотя бы одно реб­ро.

Если маршрут S имеет как начальную вершину , так и конечную вершину , то можно записать

(3)

и называть и концевыми точками или концами маршрута S. Будем говорить, что S есть маршрут длины п, соединяющий и . Если , то маршрут будет называться циклическим.

Маршрут называется цепью, а циклический маршрут - циклом, если каждое его ребро встречается в нем не более одного раза; вершины в цепи могут повторяться и несколько раз. Нециклическая цепь называется простой цепью, если в ней никакая вершина не повторяется. Цикл с концом назы­вается простым циклом, если не является в нем промежуточной верши­ной и никакие другие вершины не повторяются.

Теорема. Для того чтобы граф G представлял собой простой цикл, необходимо и достаточно, чтобы каждая его вершина имела сте­пень 2.

Для ориентированного графа можно вводить как неориентированные маршруты, цепи и простые цепи, не принимая во внимание ориентации ре­бер, так и ориентированные маршруты (цепи, простые цепи), в которых все ребра (2) проходятся в направлении их ориентации. Ориентированную цепь называют также путем, а ориентированный цикл - контуром.

Пусть граф G - неориентированный. Две вершины и называются связанными, если существует маршрут вида (1) с концами и . Граф называется связным, если любая пара вершин связана. В противном случае он является несвязным. Любой несвязный граф является совокупностью связных графов, которые обладают тем свойством, что никакая вершина од­ного из них не связана путем ни с какой вершиной другого. Каждый из этих графов называется компонентой графа G.

Пусть G - связный неориентированный граф. Так как две любые вер­шины и связаны, существуют простые цепи с концами и . Длины этих простых цепей являются неотрицательными числами. Сле­довательно, между и должны существовать цепи наименьшей длины. Эта наименьшая длина называется расстоянием между и . Допустим, по определению, . Для конечных связных графов можно также ввести протяженность между двумя вершинами и как длину самой длинной связывающей их простой цепи.

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)