Вид графов, используемых в теории электрических цепей, химии, вычислительной технике и в информатике. Основные свойства деревьев. Неориентированный граф. Алгоритм построения минимального каркаса. Обоснование алгоритма. Граф с нагруженными ребрами.
Пусть z - первая из таких вершин при движении от вершины x к вершине y и пусть m1(x, z) и m2(x, z) - части цепей m1 и m2, взятые от вершины x до вершины z. Предположим теперь, что соотношение верно для всех графов, удовлетворяющих 3 и имеющих меньше, чем p вершин, и докажем его для графа G с p вершинами. Для любой из p - l вершин, не принадлежащих циклу m, существует инцидентное ей ребро, лежащее на кратчайшей цепи (т.е. цепи минимальной длины), идущей от данной вершины к некоторой вершине цикла m. Если вершины x1 и x2 инцидентны одному такому ребру e, то e = (x1, x2), и кратчайшая цепь m1 для вершины x1 проходит через вершину x2, а кратчайшая цепь m2 для вершины x2 проходит через вершину x1 (рис. Если граф G не является связным, то возьмем вершины x и y из различных компонент связности графа G и соединим их ребром e.
Список литературы
1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗОВ / Под ред. В.С. Зарубина, А.П. Крищенко.- М.: изд-во МГТУ им. Н.Э. Баумана, 2001.- 744 с. (Сер. Математика в техническом университете; Вып XIX).
2. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.- М.: Наука, Физматлит, 2000.- 544 с.- ISBN 5-02-015238-2.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
