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

128 ' Длиной конечной цепи Z(v, и), соединяющей вершины v и и, считается число ребер в Z(v, и). Длиной конечного пути P(v, и) из. вершины v до вершины и, считается число дуг в P(v, и). Расстоянием d(v,u) между вершинами v и м графа G называется длина кратчайшей простой цегш, соединяющей их, если же вершины v и м не соединены, то полагаем d(v,u)=oo. Расстоянием d(v,u) между вершинами v и w орграфа, считается длина кратчайшего простого пути, идущего из вершины v до вершины ы; если вершина и недостюкима из v, то полагаем d(v,u)=oo. В некоторых графах вводят веса или длины ребер и дуг. В графе G(V,X) каждому ребру x-(v,u) может приписываться число /.i(v,uj, которое называется длиной или весом ребра. В орграфе G(V,JQ каждой дуге x={v,u) может приписываться число ц(у,и), которое называется длиной или весом дуги. Граф (орграф), для каждого ребра (дуги) которого определена длина, называется взвешенным графом (орграфом). Для взвешенного графа длиной конечной цепи Z(y, и), соединяющей вершины V и м, считается сумма длин всех ребер из Z(v, и). Для взвешенного орграфа длиной конечного пути P(v, и) из вершины v до вершины и, считается сумма длин всех дуг из P(v, и). Расстоянием d(v,u) между вершинами v и м взвешенного графа (орграфа) G назьшается длина кратчайшей простой цепи (кратчайшего простого пути), идущей (идущего) из вершины v до вершины м; если же вершина и не достижима из v, то полагаем d(v,u)=co. § 5. Связность графа. Компоненты связиости Пусть G - неориентированный граф, Две вершины v и м называются связанными, если существуют цепь Z(v,u) с концами v и и. Если цепь Z(y,u) проходит через какую-нибудь вершину w более одного раза, то ясно, что можно удалить циклический участок, при этом останется простая цепь, соединяющая v и и. Граф называется связным, если любая пара вершин связана (соединена простой цепью). Ясно, что связность графа G означает, что любые две его вершины являются достижимыми одна из другой. Если в графе G вершина v связана с вершиной и, то, очевидно, что и связана с v. Также очевидно, что если вершина v связана с м, а м с w, то v связана с w. Кроме того, можно считать, что v связана с v. Таким образом, отнашение связанности для вершин графа обладает свойствами симметричности, транзитивности и рефлексивности, следовательно, является отношением эквивалентности. Тогда множество V вершин графа разбивается единственным образом на попарно не пересекающиеся подмножества Vi и • Все вершины в каждом Vi связанные, а вершины из различных F; не