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

Цепь — конечная или бесконечная последовательность ребер 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-х компонент сильной связности, приведен ниже

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

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

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

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

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