Лекция п Графы. Орграфы. Графы и орграфы. Основные понятия

частью) графа G(V,E), если V V, E E. Если V=V, то G называется остовным подграфом G.
Аналогично, как и для графа, для орграфа вводится понятие ориентированный подграф.
Пример 7.1. Дан неориентированный граф.


Определение 7.4. Граф называется полным, если любые две его вершины соединены ребром. Полный граф с n вершинами обозначается через K_n.

Определение 7.5. Граф G=G(V, E) называется двудольным, если V можно представить как объединение непересекающихся множеств, скажем V=AB, так что каждое ребро имеет вид (v_i, v_j), где v_iA и v_jB. Двудольный граф называется полным двудольным графом K_{m, n}, если A содержит m вершин, B содержит n вершин и для каждого v_iA, v_jB имеем (v_i, v_j)E.

Пример 7.2. Построить полный двудольный граф K_2,4 и полный граф K₄.



7.2. Связность графов.

Определение 7.6. Пусть G=G(V, E) – граф с вершинами v₀, v₁, v₂, …, v_nV и ребрами e₁, e₂, …, e_mE. Маршрутом (путем) длины k из v₀ в v_k (или между v₀ и v_k) называется последовательность v₀e₁v₁e₂v₂e₃v₃…v_k-1e_kv_k такая, что e_i=(v_i-1, v_i).

Таким образом, путь длины k имеет k ребер. По причине избыточности обозна-чений в этом определении для графа в общем случае путь будет обозначаться через v₀v₁v₂…v_k.

Если все ребра различны, то путь называется цепью. Если все вершины различны (а значит, и ребра), то путь называется простой цепью. Замкнутая цепь называется циклом. Замкнутая простая цепь называется простым циклом. Граф без циклов называется ациклическим.

Аналогично, как и для графа, для орграфа вводятся понятия ориентированный путь, ориентированный цикл.

Пример 7.3. Дан неориентированный граф.


Определение 7.7. Граф G=G(V, E) называется связным, если имеется цепь между любыми двумя его различными вершинами.

Для заданного ориентированного графа G можно построить неориентированный граф такой, что каждая ориентированная дуга G (исключая петли) станет неориентированным ребром графа . В таком случае граф называется соотнесенным графом орграфа G(V, E).