Цепи и циклы графов

Цепь — конечная или бесконечная последовательность ребер S= (… n₁,n₂,…), в которой у каждого ребра n_к одна из вершин явля­ется вершиной ребра n_к-1, при этом ребро и одна из вершин могут встречаться несколько раз. Каждая цепь имеет начальную и конеч­ную вершину, остальные вершины называются внутренними (про­межуточными).

Цепь называется простой, если любое реьро не повторяется в цепи дважды. Составной (сложной) в противном случае; элементар­ной, если в ней ни одна из вершин не повторяется дважды.

Цикл — конечная цепь, начинающаяся и заканчивающаяся на той же вершине.

Цикл называется простым, если все его ребра различны, в ином случае — составным (сложным), и элементарным — если при об­ходе его ни одна из вершин не встречается дважды.

Цикл, не содержащий вершины, кроме той, на которой он начи­нается и заканчивается, называется петлей.

Цикл, у которого начальная и конечная вершины различны, на­зывается путем.

Он также может быть простым (никакая дуга не встречается дважды), составным или элементарным (никакая вершина не встре­чается дважды).

Длина пути — число ребер (дуг) в нем.

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

Граф называется конечным, если число вершин его конечно, и бесконечным — в ином случае.

Граф Н (v,u,j) называется частичным для графа G (v,u,j), если все ребра и вершины графа Н, являются соответственно ребрами и вершинами графа G, т.е. если Н Ì G, то для всех n Î V.

Нуль-граф считается частичным графом любого графа. Все частичные графы Н_i для G (v,u,j) можно получить, выбирая в качестве ребер всевозможные подмножества ребер графа G.

Подграфом G_А (А) графа G (v) называется граф, вершинами кото­рого являются вершины А Ì v, а ребрами — все ребра из G, оба конца которых лежат в А.

Иначе, G_А (А) подграф графа G (v), если А Ì v и G_А (v)= G (v)Ç А.

Если А = v, то G_А (А)= G (v); если А ={ а }, т.е. А состоит из одной вершины, то G_А (а) состоит из петель в а; если А Ì v — подмножество изолированных вершин графа G (v), то подграфом графа G (v) будет нуль-граф.

Частичным подграфом Н_А (А), А Ì Х графа G (v) называется подграф, ребрами которого являются некоторые ребра из G (v), оба конца которых лежат в А.

Иначе, Н_А (А) — частичным подграф графа G (v), если А Ì Х и Н_А (v)= G (v)Ç А для всех v Î V.

Дополнительным частичным подграфом Н_А (А) графа G (v) является единственный граф, состоящий из ребер графа G (v), не принадлежащих некоторому частичному подграфу Н_А (А) графа G (v).

1 - Граф G (v).

2 - Подграф G_А (А) графа G (v).

3 - Частичный подграф Н_А (А) графа G (v).

4 - Дополнительный частичный подграф Н_А (А) графа G (v).

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

Две вершины n_i и n_j неорганизованного графа G (v) называются связными, если существуюет цепь S с концами n_i и n_j. При прохож­дении пути через некоторую вершину n_к более одного раза цикл в вершине n_к можно удалять из цепи S.

Неориентированный граф называется связным, если любая пара его вершин связана. Отношение связности для вершин графа явля­ется отношением эквивалентности. Оно разбивает множество вер­шин графа на классы.

Подграфы, ''натянутые'' на эти классы вершин, называются компонентами связности графа. Другими словами, компонентами связности неориентированного графа G (v) называется подграф Н_А (А) с множеством вершин А Ì v и множеством ребер в G (v), инцидентных только вершинам из А, причем ни одна из v_i Î A не смежна с верши­нами из множества v Ç А.

Несвязный граф состоит из нескольких отдельных частичных подграфов:

В сильно связанном ориентированном графе для любой пары вершин обязательно существует соединяющий их путь. Компонентой сильной связности ориентированного графа G (v) называется сильно связанный подграф Н_А (А) с множеством вершин А Ì v и множеством дуг, имеющих начало и конец в множестве А, причем ни одна из вершин v_i Î A и ни одна из вершин v_j Î v Ç А не смежны между собой. Очевидно, что сильно связанный ориентированный граф имеет только одну компоненту сильной связности. Пример ориентированного графа, состоящего из 2-х компонент сильной связности, приведен ниже

Отдельными, широко используемыми видами графов являются деревья и прадеревья.

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

Такой граф не имееи кратных ребер:

Ветвями дерева называются ребра графа, входящие в дерево.

Хордами дерева называют ребра, взодящие в граф, дополнительный к данному графу.