31.Маршруты, пути.

Маршрутом в графе называется чередующаяся последовательность вершин и рёбер vo,e1,v1,e2,v2,... ,efc,Vfc, в которой любые два соседних элемента инцидентны. Если vo = Vk, то маршрут замкнут, иначе открыт. Если все рёбра различны, то маршрут называется цепью. Если все вершины

(а значит, и рёбра) различны, то маршрут называется простой цепью. В цепи vo,ei,... ,еk-1, Vk вершины vq и Vk называются концами цепи. Говорят, что цепь с концами u и v соединяет вершины u и v. Цепь, соединяющая вершины u и v, обозначается (u,v). Очевидно, что если есть цепь, соединяющая вершины u и v, то есть и простая цепь, соединяющая эти вершины. Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Число циклов в графе G обозначается z(G). Граф без циклов называется ациклическим. Для орграфов цепь называется путем, а цикл — контуром.

32.Матричное задание графов.

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

Граф (неориентированный или ориентированный) может быть представлен в виде матрицы типа nхm, где n — число вершин,a m — число ребер (или дуг). Для неориентированного графа элементы этой матрицы задаются следующим образом: .

Более эффективной матричной структурой, представляющей граф, служит матрица смежности вершин, или булева матрица графа. Это квадратная матрица В порядка n, элементы которой определяют следующим образом:

для неориентированного графа Заметим, что в k-й строке матрицы ориентированного граграфа количество единиц равно полустепени исхода dg+ v_k вершины v_k, а количество единиц в k-м столбце dg- v_k — полустепени захода Для неориентированного графа матрица смежности вершин симметрическая.

33.Операции над графами, подграфы.

Объединением графов G₁(V₁, E₁) и G₂(V₂, E₂)  называется граф G(V, E) =  , где  V =  , E =  .Пересечением графов G₁(V₁, E₁) и G₂(V₂, E₂)  называется граф G(V, E) =  , где V =    E =  Дополнением графа  G₁(V₁, E₁) называется граф G(V, E) =  , где   ,  E =  Кольцевой суммой графов  G₁(V₁, E₁) и G₂(V₂, E₂)  называется граф G(V, E) =  , где V =  , E =  . Подграфом графа G(V, E) называется граф G ¢(V ¢, E ¢),  где    . Подграф   называется остовным подграфом графа G(V,E), если  . Подграф    называется собственным подграфом граф G, если  .

34.Связанность, компоненты связанности, матрица связанности, выделение компонентов связанности.Две вершины называются связными, если существует маршрут между ними. Связность для вершин является бинарным отношением. Неориентированный граф называется связным, если между любыми двумя вершинами есть маршрут. Любой граф G можно разбить на непересекающиеся подмножества вершин по признаку связности. Вершины одного множества являются связными между собой, а вершины различных множеств – несвязны. Тогда все выделенные таким образом подграфы называют компонентами связности графа G. При этом связный граф имеет одну компоненту связности. Матрица сильной связности ориентированного графа D − квадратная матрица S(D)=[s_ij] порядка n, элементы которой равны

Матрица связности графа G − квадратная матрица S(G)=[s_ij] порядка n, элементы которой равны