4.3. Операции над частями графа

Граф Н называется частью графа G, HG, если множества его вершин и ребер V(H) и E(H) содержатся соответственно в V(G) и E(G). Если V(G) = E(G), то часть H графа G называется суграфом.

Суграф Н является перекрывающим для н-графа G, если любая вершина графа G инцидентна хотя бы одному ребру из H.

Подграфом G(V) графа G(V) с множеством вершин V V называется часть, которой принадлежат все ребра с обоими концами из H.

Над частями графа G производятся следующие операции:

1. Дополнение к части H определяется множеством всех ребер G, не принадлежащих Н:

E(H)E( )=; E(H)E( )=E(G)

2. Сумма H₁  Н₂ частей H₁ и Н₂ графа G:

V(H₁  Н₂)=V(H₁) V(H₂); E(H₁  Н₂)= E(H₁) E(Н₂)

3. Произведение H₁  Н₂:

V(H₁  Н₂)=V(H₁) V(H₂); E(H₁  Н₂)= E(H₁) E(Н₂)

Две части Н₁ и Н₂ не пересекаются по вершинам, если V(H₁) V(H₂)=  а следовательно, и нет общих ребер: E(H₁) E(Н₂)= 

Части Н₁ и Н₂ не пересекаются по ребрам, если E(H₁) E(Н₂)= 

Если Н₁ и Н₂ не пересекаются по вершинам, то сумма называется прямой.

4.4. Маршруты, пути, цепи, циклы

Пусть G - н-граф.

Маршрутом в G называется такая последовательность ребер M(е₁, е₂,…, е_n) в которой два соседних ребра е_i-1 и e_i имеют общую вершину. В маршруте одно и то же ребро может встречаться не­сколько раз. Начало маршрута - вершина V₀, инцидентная ребру e_{1 ­­­} и не инцидентная ребру е₂; конец маршрута V_n инцидентен e_n и не инцидентен e_n-1. Если е₁, е₂ (e_n-1, e_n) - кратные , требуется дополни­тельное указание, какую из двух инцидентных вершин считать нача­лом (концом) маршрута.

Маршрут, в котором совпадают начало и конец V₀=V_n назы­вают циклическим. Маршрут, в котором все ребра разные называют цепью. Цепь, не пересекающая себя (без повторяющихся вершин), называется простой цепью.

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

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

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

Теперь пусть G-орграф.

Последовательность ребер, в которой конец каждого предыдущего ребра е_i-1 совпадает с началом следующего e_i, называют пу­тем. В пути одно и то же ребро может встречаться несколько раз.

Началом пути является начало e₀, концом – конец e_n, т.е. вер­шины v₀ и v_n .

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

Контур – путь, в котором v₀ = v_n. Контур называется цик­лом, если он является цепью, и простым циклом, если это простая цепь. Если граф содержит циклы, то он содержит и простые циклы: граф без циклов называется ациклическим.

Вершина vG называется достижимой из вершины vG если имеется путь L(v,…,v) с началом v и концом v.

Орграф называется связным если он связан без учета ориента­ции дуг, и сильно связным, если из любой вершины v в любую вер­шину v существует путь. Число ребер пути называется его длиной.

Расстоянием (v’,v) между вершинами v и v н-графа G называется минимальная длина простой цепи с началом v и концом v.

Центром называется вершина н-графа, от которой максимальное расстояние до других вершин являлось бы минимальным. Максимальное расстояние от центра G до его вершин называется ра­диусом графа r(G).

Эйлеров цикл – цикл графа, содержащий все ребра графа.

Эйлеров граф – граф, имеющий эйлеров цикл (эйлеров цикл можно считать следом карандаша, вычерчивающего этот граф без отрыва от бумаги).

Имеет место теорема Эйлера: конечный неориентированный граф G – эйлеров тогда и только тогда, когда он связан и сте­пени всех его вершин четны.

Эйлерова цепь – цепь, включающая все ребра данного конечного н-графа G, но имеющая различные начало v' и конец v. Чтобы в конечном н-графе G существовал эйлеров цикл, необхо­димы и достаточны его связанность и четность степеней всех вер­шин, кроме начальной v' и конечной v (они должны иметь нечетные степени). Чтобы в конечном орграфе существовал эйлеров цикл, необходима и достаточна его связность, а также равенство степеней вершин этого графа по входящим и выходящим ребрам, т.е. ₁(V) = ₂(V),

 V G.

Гамильтонов цикл – простой цикл, проходящий через все вершины рассматриваемого графа. Гамильтонова цепь – простая цепь, проходящая через все вершины графа с началом и концом в разных точках.