Дискретная математика

127 Так как в последовательности нет ребер, предшествующих xi, то vo называется начальной вершиной цепи, а если нет ребер, следующих за х„, то v „ называется конечной вершиной.. Любая вершина принадлежащая двум соседним ребрам и х^, называется внутренней или промежуточной вершиной. Так как ребра и вершины в цепи могут повторяться, то внутренняя вершина может также оказаться начальной или конечной. Любой участок цепи есть цепь. Нупъ-цепъ - цепь, не содержащая никаких ребер. Нетривиальная цепь - это цепь, содержащая хотя бы одно ребро. Если цепь имеет начальную вершину vo и конечную вершину то записываем: Z=Z(VU,VJ. Вершины Vo и Vk называются концами цепи. Простая цепь - это цепь, все вершины которой, кроме, быть может, первой и последней, попарно различны и все ребра попарно различны. Вершина и (неориентированного) графа G называется достижимой из вершины V, если существует цепь Z(v,u), соединяющая эти вершины. Легко видеть, что отношение достижимости в графе G обладает свойствами рефлексивности, симметричности н транзитивности, следовательно, является отношением эквивалентности. Если_ vt=VQ, т.е. начало и конец цепи совпадают, то цепь называется циклической или замкнутой. Замкнутая цепь называется простьш цикло.ч, если все его п вершин различны и и >5. Для орграфа вместо цепи и цикла вводят понятия пути и контура. Путь в орграфе - это конечная или бесконечная черед^тащаяся последовательность вершин и дуг vo, xi, v/, Х2, v ^ , v „ . / , x^ в которой каждая дуга х, есть (v,.;, v, ). Таким образом, путь в орграфе это последовательность вершин У Д , V ;, VJ . ..., такая, что для любого / (; > 0) из V, идёт дуга в v,-/, если v,v/ существует. Каждый путь ориентирован от начальной вершины к последующей. Простой путь в орграфе - это путь, все вершины которого, кроме, быть молсет, первой и последней, попарно различны. Замкнутый путь это путь, первая и последняя вершины которого совпадают. Контур - нетривиальный замкнутый путь, у которого все верпшны различны за исключением первой и последней. Если в орграфе G существует путь из вершины v в вершину и, то считается, что и достижима ш v. Отношение достижимости в орграфе G обладает свойствами рефлексивности и транзитивности. *) В ряде работ вводится понятие маршрута, которое совпадает с введенным понятием цепи, но при 3T0i\! цепь вводится как маршрут беч повторяющихся ребер