Спирина, М.С. Дискретная математика

том длины к - 1. Маршрут принято задавать как последователь­ ность ребер, поскольку это более удобно при наличии кратных ребер- Если начальная вершина маршрута совпадает с конечной, то такой маршрут называется замкнутым или циклом. В графе G4 (рис. 2.1, г) (/, s, р, г), (и, s, t, г) — циклы длиной 4, (г, t, q, s, и) —цикл длиной 5, (/, 5, и, г, t, s, р, г) — 8-цикл, (р,и ) — 2-цикл, петля ( q ) — 1 -цикл. Расстоянием между двумя вершинами называется минималь­ ная длина из всех возможных маршрутов между этими вершина­ ми при условии, что существует хотя бы один такой маршрут. Обозначается как d( К, У2) (от лат. distantio —расстояние) d( К, У2) = = m in |F , . . .F 2|. Поскольку рассматриваются конечные графы, минимум мож ­ но найти всегда. Очевидно, что d( У\У2) =d( У2Vx). Формально можно ввести расстояние d(V 'V ') - 0 между любой вершиной и ей же самой, что соответствует нулевому маршруту, у которого начало и конец в одной вершине. В маршруте одно и то же ребро может встретиться несколько раз. Если ребро встретилось только один раз, то маршрут называ­ ется цепью. Например, в графе G4 (рис. 2.1, г) (t, s, р) — 3-цепь. Если (хц х2, ..., хк. х, х к) — Л-цикл, то любая циклическая переста­ новка, например (х2, ..., хк_х, хк, Xj), также будет циклом, п о ­ скольку сведется лишь к выбору начальной вершины. Частным случаем этого утверждения будет следующее: если /г-цикл (х1; х2, ..., хк_х, хк) является цепью, то для любой циклической подстановки о е Sk последовательность (ха<|), ха(2), ..., хаХк)) также будет ^-циклом и цепью. В орграфе маршрут является ориентированным и называется путем. На путь сразу налагаются важные требования, являющиеся частью определения: • направление каждой дуги должно совпадать с направлением пути; • ни одно ребро пути не должно встречаться дважды. Другими словами, путь — упорядоченная последовательность ребер ориентированного графа, в которой конец предыдущего ребра совпадает с началом следующего и все ребра единственны. На рис. 2.3 (и, s, г, t) — 4-путь, (г , и) — 2-путь, (s, г, t, s) путем не является. Тогда цикл в орграфе — путь, у которого совпадают н а ­ чало и конец. На рис. 2.3 ( s , г, t) и (и, s, г) — 3-циклы. Для циклов орграфа также справедлива теорема о циклических подстановках. Цепь, путь и цикл в графе называются простыми, если они проходят через любую из вершин не более одного раза. Неориен­ тированный граф называется связным, если между любыми дву ­ мя его вершинами есть маршрут. Для связного графа ориентация дуг не обязательна. Так, граф G2 (рис. 2.1, б) является связным, а граф G4 (рис. 2.1, г) — несвязным. Также можно ввести понятие 73