Определение графа. Операции с графами. Связность графа, сильно связный граф. Транзитивное замыкание

Граф – совокупность двух множеств G = (V, X), где V = {v₁, …, v_n} – множество вершин, X={(v_i, v_j) | v_i, v_j Î V} – множество ребер т.е. граф – совокупность вершин и соединяющих их ребер. При этом дуга (v_i, v_j) называется исходящей из вершины v_i и заходящей в вершину v_j.

(v, v) – петля.

Псевдограф – граф с кратными (одинаковыми) ребрами и петлями.

Мультиграф – псеводограф без петель.

Элементарный граф (или просто граф) – мультиграф с кратностью ребер =1.

Неориентированный граф – граф, пары множества X которого неупорядочены, называются ребрами.

Ориентированный граф – граф, у которого пары множества Х упорядочены, называются дугами, обозначаются (v,w). Орграф можно задать как D=(V, Г), где Г – многозначное отображение множества вершин в себя, V – множество вершин.

Г: Г_v1={v₂} – т.е. вершине, которая достижима из v₁.

Операции с графами:

1)Объединение графов G₁ (V₁, X₁) и G₂ (V₂, X₂) называется граф G₁ È G₂ = (V₁ È V₂, X₁ È X₂) [т.е. граф, содержащий все вершины и дуги графов G₁ и G₂].

2)Пересечение графов G₁ (V₁, X₁) и G₂ (V₂, X₂) называется граф G₁ Ç G₂=(V₁ Ç V₂, X₁ Ç X₂) [т.е. граф, содержащий все вершины и дуги, принадлежащие одновременно графам G₁ и G₂].

3)Декартово произведение орграфов G₁ (V₁, X₁) и G₂ (V₂, X₂) называется граф G₁ x G₂ = (V₁ x V₂, Г), где для каждой вершины U = (v, w) Î V: Г_u = Г_v x Г_w.

4)Декартова суммаграфов G₁ (V₁, X₁) и G₂ (V₂, X₂) называется граф G₁ + G₂ = (V₁ x V₂, Г), где для каждой вершины U = (v, w) Î V: Г_u = {v}x Г_w È Г_v x {w}.

Связность графа, сильно связный граф:

Неориентированный граф G называется связным, если существует путь между любыми двумя его вершинами v_i и v_j. (любая его вершина достижима из другой вершины)

Ориентированный граф D называется сильно связным, если любые две его вершины v_i и v_j взаимодостижимы [т.е. существуют пути из v_i в v_j и из v_j в v_i].

Орграф D называется односторонне связный, если для любых двух его вершины v_i и v_j хотя бы одна достижима из другой.

Орграф D называется слабосвязным, если ассоциированный с ним неориентированный граф G является связным (получается замещением дуг на ребра)

Если орграф D не является сильноявязным, то его можно разбить на сильносвязные подграфы. (компонента сильной связности, точка сочленения, мост)

Транзитивное замыкание.

Г_v – образ вершины v. Г_v² – образ вершин которые достижимы из v (находятся в образе вершины v)

Прямым транзитивным замыканием вершины v называется множество вершин, достижимых из v.

Г_v^-1 – прообраз вершины v. Г_v² – прообраз вершин которые являются прообразами v (те, из которых достижима v)

Обратным транзитивным замыканием вершины v называется множество вершин, из которых достижима v.