Информационные технологии проектирования электронных средств

- 20 - Несвязный граф G состоит из подграфов G 1 ,G 2 ,…,G n , любой из которых называется компонентом связности. Связный граф состоит из единственного компонента связности. Точка сочленения (разделяющая вершина) – такая точка, удаление кото- рой из графа увеличивает число его компонент связности. Гамильтонов цикл (ГЦ) – цикл, проходящий по всем вершинам графа G один раз. В отличие от эйлерова цикла для ГЦ не известен общий критерий его существования. Рис. 7 Рис. 8 Деревом Е ( X,E ),  X  = n называется связный граф без циклов. Любое де- рево имеет n -1 ребро. В дереве существует начальная вершина, которая называ- ется корнем дерева. Любые две вершины в дереве x i и x j связаны единственной цепью. Лес – это множество деревьев графа G . Для задачи конструирования ЭС интерес представляют деревья, у кото- рых n равно числу вершин графа G , из которого выделено это дерево. Они называются покрывающими деревьями. Задачи выделения эйлерова и гамильтонова циклов, а также покрывающих деревьев связаны с задачами построения цепей или маршрутов, содержащих кратчайшее число ребер. Это кратчайшие покрывающие деревья (КПД). 1 x 5 x 4 x 2 x 3 x 1 x а ) 5 x 2 x 3 x 1 x б ) 5 x 4 x 2 x 3 x 1 x в )