Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 106 стр.

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                            .




                  Рис. 7.2. Дополнение графа, изображенного на рис. 7.1.


    Если каждому ребру графа ставится в соответствие некоторое число, то
оно называется весом ребра, а граф называется взвешенным.
    Путь, соединяющий вершины u и v – это последовательность вершин v0,
v1… vn, где v0=u, а vn= v и для любых i = 0…n вершины vi и vi+1 соединены ре-
бром. Если граф взвешенный, то длиной пути называется сумма весов его ре-
бер. Путь называется замкнутым, если v0 = vn. Цикл – это замкнутый путь, в
котором ни одно ребро не повторяется дважды. Простой цикл – это цикл, в
котором ни одна вершина не повторяется дважды.
    Расстояние между двумя вершинами – это длина кратчайшего пути, со-
единяющего эти вершины.
    Деревом называется связный граф без циклов.




                   Рис. 7.3. Пример дерева – связного графа без циклов.
    Те деревья, которые были рассмотрены в предыдущем разделе, являются
частным случаем такого графа с выделенной корневой вершиной и направ-

                                           106