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

149 Поясним это на примере. Пусть зада140, что четыре города расположены в вершинах квадрата с единичной стороной. В случае, если этот граф имеет ребрами только стороны квадрата, то остовное дерево с минимальной мерой представлено на рис. 5.22, а) и его мера jufT) = 3. УЗ а) VF V/ V2 v j V4 б) VI V2 Рис. 5.22 Введем новую вершину на пересечении диагоналей квадрата. Тогда остовное дерево с минимальной мерой представлено на рис. 5.22, б) и его ме р а f4(T) =2 72=2,828. Если ввести две новые вершины (точки разветвления), то оптимальное остовное дерево, представленное на рис. 5.22, в ) , имеет меру 1л(Т) =2,732. Таким образом, нужно четко представлять цель исследования. Нельзя судить о дереве по его коре. Английская пословица а) Ш ® Рис. 5.23 § 12. Центры дерева Пусть кюкдое ребро графа G имеет единичную длину. Длина цепи, соединяющей вершины V и W, в этом случае, равна числу ребер этой цепи. Пусть v - • некоторая вершина дерева G, от которой можно прийти к любой другой вершине и, при этом длину цепи обозначим через d(v,u). Максимальное из этих величин d(v,u) по всевозможным и е G называется эксцентриситетом вершины v и обозначается как e(v). Итак, эксцентриситет вершины v равен числу е(у) = maxd(v,u). На рис. 5.23, а) приведён rpaf" iieG (дерево), для вершин v и и которого, очевидн имеем: е{у) = 3, е(м) = 2. Наибольший из эксцентриситетов вери