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

160 G, t s t s V • ® GI и Рис. 5.33 Толщина планарного графа равна 1. Можно доказать, что нижняя оценка толщины t{G) графа с п вершинами определяется неравенством: здесь Jx[ - целая часть от х, а degfvj - локальная степень вершины v „ 1 < z < п . Дан (неориентированный) взвешенный связный граф G(V,X). Каждому ребру л графа приписан вес (длина) /и(х) ребрах. В частном случае 1л(х) может быть расстоянием между вершинами, соединенными ребром х или временем проезда по этому ребру, или стоимостью проезда по этому ребру и т.п. Длиной цепи Z(v,u), как известно, считают сумму длин ребер данной цепи. Требуется для двух произвольных вершин v и к графа G найти цепь Z(v, и) такую, чтобы его длина была наименьшей. Решим прелсде частный случай этой задачи. Нахождение кратчайшей цепи между произвольными вершинами в графе с ребрами единичной длины. Пусть у графа G все ребра имеют одинаковую длину, принимаемую за единицу. Будем считать, что заданы вершины V и и. Как уже отмечено, все задачи на конечных графах можно решить простым перебором, но это громоздко и не всегда (в большинстве случаев) /I t(G)> 1 +7 ГZ deg(vJ-2)/(6(n.2))f. Дорога беэ поворотов длинна. Английская пословш^а § 17. Задача о кратчайшей цепи между произвольными вершинами графа