назад

3.3 Цепи. Циклы. Связность

Маршрутом в G называется такая последовательность ребер M(l1, l2, : ln), в которой каждые два соседних ребра li-1 и li имеют общую вершину. Начало маршрута - вершина ν0, инцидентная ребру l1 и неинцидентная l2, конец маршрута νn инцедентен ln и неинцедентен ln-1.

Маршрут, в котором совпадают его начало и конец ν0n, называется циклическим.

Маршрут, в котором все ребра разные, называется цепью. Цепь, не пересекающая себя, т.е. не содержащая повторяющихся вершин, именуется простой цепью.

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

Вершины ν', ν'' G, называется связанными, если существует маршрут М с началом ν' и концом ν''. Связанные маршрутом вершины связаны также и простой цепью. Отношение связанности вершин обладает свойствами эквивалентости и определяет разбиение множества вершин графа на непересекающиеся подмножества Vi, i=1,k.

Граф G называется связным, если все его вершины связаны между собой. Поэтому все подграфы G(Vi) связны и называются связными компонентами графа.

Каждый неориентированный граф распадается единственным образом в прямую сумму своих связных компонент


Вершинной связностью (G) графа G называется наименьшее число вершин, удаление которой делает граф несвязным или одновершинным. Для всех G (G)=0

Реберной связностью (G) графа G называется наименьшее число ребер, удаление которых приводит к несвязному графу. Для несвязного или одновершинного графа (G)=0.

Удаление вершины из графа G приводит к подграфу G-V, содержащему все вершины графа G, кроме М и ребра графа G, неинцедентных V.

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

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

Длина кратчайшего маршрута (простой цепи) между νi и νj называется расстоянием между вершинами и обозначается L(νiνj). Для фиксированной вершины xi величина
Е(νi)= l(νi)
называется эксцентриситетом вершины νi.

Максимальный среди всех эксцентриситетов эксцентриситет вершины называется диаметром графа G и обозначается через d(G). Следовательно
d(G)=l(νiνj)

Вершина νi называется периферийной, елси l(νi)=d(G). Простая цепь длины d(G) называется диаметральной цепью.

Минимальный из эксцентриситетов вершин связного графа G называется его радиусом и обозначается r(G).
r(G)=l(νi)=l(νi), l(νj)

Последовательность ребер, в которой конец любого предыдущего ребра li-1 совпадает с началом следующего li, называется путем. Началом пути является начало ν0 ребра l1. Концом пути - конец νn ребра ln. В пути одно и то же ребро может встречаться несколько раз.

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

Контур - путь, в котором ν0n. Контур называется циклом, если он является цепью и простым циклом, когда это простая цепь.

Граф, не содержащий циклов, называется ациклическим. Вершина ν'' G называется достижимой из вершины ν', если существует путь d(ν', ν'') с началом ν' и концом ν''.

Орграф G именуется связным, если он связен без учета ориентации дуг, и сильно связен, если из любой вершины ν' в любую ν'' существует путь.

Число ребер маршрута (пути) называется его длиной.

Расстоянием d(ν', ν'') между вершинами ν' и ν'' неориентированного графа G называется минимальная длина простой цепи с началом ν' и концом ν''. Центром называется вершина неориентированного графа, от которой максимальное из расстояний до других вершин являлось бы минимальным. Максимальное расстояние от центра G до его вершин называется радиусом графа r(G).

Эйлеров цикл - цикл графа, содержащий все ребра графа.

Эйлерова цепь - цепь, включающая все ребра данного конечного неориентированного графа G, но имеющая различные начало ν' и конец ν''.

Чтобы в конечном неориентированном графе G существовала эйлерова цепь, необходимы и достаточны его связность и четность степеней всех вершин, кроме начальной ν' и конечной ν''' и ν'' должны иметь конечные степени). Чтобы в конечном графе существовал эйлеров цикл, необходимы и достаточны его связность, а также равенство степеней вершин этого графа по входящим и выходящим ребрам, т.е. ρ1(ν)=ρ1(ν), ν G.

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

Гамильтонова цепь - простая цепь, проходящая через все вершины графа с началом и концом в разных вершинах ν1, ν2 G.


Рисунок 1

Для вершин ν1, ν2 G на рисунке 1
  1. Маршрут является цепью (l1 l2 l3 l4 l5 l1 l8 l7 l6 l1 l8 l7) или (l1 l2 l3 l4 l5 l1 l8 l7).
  2. Цепь не является простой цепью (l1 l2 l3 l4 l5 l6).
  3. Простая цепь (l1 l6) или (l8 l7).

Для вершины ν1

  1. циклический маршрут не является циклом (l1,l2,l3,l4,l5,l2,l3,l4,l5,l6,l7,l8,l1,l6,l7,l8)
  2. Цикл не являтся простым циклом. (l1,l2,l3,l4,l5,l6,l7,l8).
  3. Простой цикл (l1,l6,l7,l8).
  4. При описании цикла в качестве его начала и конца может быть выбрана любая вершина, поэтому последовательности (l1,l6,l7,l8), (l6,l7,l8,l1), (l7,l8,l1,l6), (l8,l1,l7,l6) представляют один и тот же цикл.

Свойства отношений связности вершин графа

Пример

Рисунок 2
  1. рефлективность: если вершина ν G связана с какой-либо другой вершиной ν', то она связана и сама с собой (изолированные вершины являются также связанными сами с собой);
  2. симметричность: если в графе G существует маршрут с началом ν' и концом ν'', то существует маршрут с началом ν'' и концом ν';
  3. транзитивность: если вершина ν' связана с ν'' маршрутом
    (l., ...,l.),
    1n
    а ν'' и ν''' маршрутом
    (l.., ...,l..),
    1p
    то ν' связана с ν''' маршрутом
    (l., ...,l., l.., ....,l..).
    1n1p

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

Теорема (Дирака). Если в графе G(ν, E), ν V

d(ν) p/2, то G является гамильтоновым.

Подмножества вершин S графа G=(V, U) называется доминирующим (внешне устойчивым), если каждая вершина из V - S смежна с некоторой вершиной из S. Другими словами, каждая вершина графа находится на расстоянии не более единицы от доминирующего множества. Доминирующего множество называется минимальным, если нет другого доминирующего множества, содержащеюся в нём. Минимальных доминирующих множеств в графе может быть несколько, и они обязательно содержат одинаковое количество вершин. Минимальное доминирующее множество, имеющее наименьшую мощность, называется наименьшим.

Подмножество вершин графа, являющееся одновременно независимым и доминирующим, называется ядром графа.

Понятие доминирующего множества переносится и на случай ориентированных графов. Подмножество S вершин орграфа называется доминирующим, если для любой вершины νiV-S существует такая вершина νj S, что (νi, νj)A, где A - множество дуг орграфа. Подмножество вершин S, являющееся одновременно и независимым, и доминирующим, называется ядром орграфа.

Например, орграф на рис. 3(а) имеет два ядра S1={1, 3}; S2={2,4}.

Орграф, изображенный на рисунке 3(б) не имеет ядра.


Рисунок 3 - Ориентированные графы

Вершина и ребро графа покрывают друг друга, если они инцидентны. Ребро (νi, νj) покрывает вершины νi и νj, а каждая из этих вершин покрывает это ребро. Подмножество SV называется покрытием (вершинным покрытием, опорой) графа G, если каждое ребро из V инцидентно хотя бы одной вершине из S. Покрытие графа G называется минимальным, если оно не содержит покрытия с меньшим числом вершин, и наименьшим, если число вершин в нём - наименьшее среди всех покрытий графа G. Число вершин в наименьшем покрытии графа G называется числом покрытия (числом вершинного покрытия) графа G и обозначается через β(G) .

Рёберным покрытием графа G называется такое подмножество рёбер WU, которое покрывает все вершины графа. При этом каждая вершина в G инцидентна по крайней мере одному ребру из W. Рёберное покрытие графа называется минимальным, если в нём не содержится покрытие с меньшим числом рёбер, и наименьшим, если число рёбер в нём - наименьшее среди всех покрытий. Число рёбер в наименьшем рёберном покрытии графа G называется числом рёберного покрытия и обозначается через β1(G).

 

Вопросы для самоконтроля

  1. Дайте определение пути, цепи, цикла.
    Определите в чем различие на примере.
  2. Сформулируйте свойства цепей.
  3. Дайте определение связности.

Практические задания

Tест для самоконтроля