48) Произведение графов. Свойства.

Пусть у нас имеются графы G₁ = (V₁,E₁) и G₂ = (V₂,E₂), произведением графов G₁ и G₂ называется граф G₃ = (V₃ ,Е₃) = G₁ * G₂. Множество вершин V₃ состоит из всех пар (v,v'), где v принадлежит V₁ и v^/ принадлежит V₂. В графе G₃ есть ребро от вершины (v₂,v^/₂) к вершине (v₂, v₂') в том, и только том случае, если графе G₁ есть ребро от v₁ к v₂ и в графе G₂ есть ребро от v₁ 'к v₂'. На Рис. 15 представлен пример произведения двух ориентированных графов.

Теорема. (изоморфны) , т.к. <1,a>→<a,1>

Операция декартова произведения обладает следующими свойствами.

1. G₁G₂ = G₂G₁ - свойство коммутативности;

2. G₁(G₂G₃) = (G₁G₂)G₃ - свойство ассоциативности.

49) Композиция графов. Некоммутативность операции композиции графов.

Пусть G1(X,E1) и G2(X,E2) — два графа с одним и тем же множеством вершин X. Композицией G1(G2) графов G1 и G2 называется граф с множеством вершин E, в котором существует дуга (xi,xj) тогда и только тогда, когда существует дуга (xi,xk), принадлежащая множеству E1, и дуга (xk,xj), принадлежащая множеству E2.

Рассмотрим выполнение операции композиции G1(G2) на графах, изображенных на рис.3. Для рассмотрения операции составим таблицу, в первом столбце которой указываются ребра (xi, xk), принадлежащие графу G1, во втором – ребра (xk, xj), принадлежащие графу G3, а в третьем – результирующее ребро (xi, xj) для графа G1(G2).

G1 G2 G1(G2)

(x1,x2) (x2,x1) (x1,x1)

(x2,x3) (x1,x3)

(x1,x3) (x3,x3) (x1,x3)

(x2,x1) (x1,x1) (x2,x1)

(x1,x3) (x2,x3)

Заметим, что дуга (x1,x3) результирующего графа в таблице встречается дважды. Однако, поскольку рассматриваются графы без параллельных ребер (дуг), то в множестве E результирующего графа дуга (x1,x3) учитывается только один раз, т.е. E = {(x1,x1), (x1,x3), (x2,x1), (x2,x3)}

На рис. 3 изображены графы G1 и G2 и их композиции G1(G2). На этом же рисунке изображен граф G2(G1). Из рисунка видно, что композиция некоммутативна G1(G2) ≠G2(G1)

Графы G1(G2) и G2(G1) не изоморфны.

50) Маршруты, цепи, циклы, простые цепи и циклы. Связность в графах. Сильно связные графы. Связные компоненты.

Маршрут в графе — это чередующаяся последовательность вершин и рёбер , в которой любые два соседних элемента инцидентны. Вершины v₀, v_k называются связанными данным маршрутом (или просто связанными). Вершину v₀ называют началом, а v_k – концом маршрута. Если , то маршрут замкнут, иначе открыт. Число k называется длиной маршрута.

Маршрут называют цепью, если все его ребра различны, и простой цепью, если различны все его вершины. Число ребер в цепи называют длиной цепи.

Замкнутую цепь называют циклом, а простую замкнутую цепь – простым циклом. Число ребер в цикле называют длиной цикла. Для орграфов цикл называется контуром. Цикл (простой цикл) в орграфе — это простой путь длины не менее 1, который начинается и заканчивается в одной и той же вершине.

Граф называется связным, если в нем для любых двух вершин имеется маршрут, соединяющий эти вершины. Заметим, что в этом определении можно заменить слово "маршрут" словами "простой путь".

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

Для ориентированных графов определено понятие сильной компоненты связности. Орграф называется сильно связным, если любые две его вершины сильно связаны. Две вершины s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Компонентами сильной связности орграфа называются его максимальные по включению сильно связные подграфы.

Свойства графов:

1°.Каждая вершина графа входит в одну и только в одну компоненту связности.

2°.Любой конечный граф имеет конечное число компонент связности.

3°.Граф, состоящий из единственной компоненты связности, является связным.

4°.Каждая компонента связности графа является его подграфом.

5°.Для любого графа либо он сам, либо его дополнение является связным.