Дискретная математика
144 1. Тогда: 2т = % deg(Vf) > 2п. Но т-п-\, т.е. 2п-2 > 2п, что не может быть. ;•=/ Таким образом, локальные степени всех вершин не могут быть больше единицы. Допустим, что существует только одна веришна с локальной степенью 1, а остальные вершины имеют локальную степень больше единицы. Тогда П вновь имеем: 2m = Y, deg(v,) >2(п-\)+\=2п-\. Но т= п-1, т.е. 2п-2 =>2«-1, что i=J не может быть. Итак, не менее чем две вершины являются висячими. Корневым деревом называется дерево с выделенной вершиной, называемой корнем. При решении некоторых задач необходимо осуществлять обход вершин графа G(V,X) для поиска вершины, удовлетворяющей заданным свойствам. Пусть Т - некоторый остовный подграф графа G(V,X), не имеющий цикла, т.е. Г - дерево и положим, что v - корень этого дерева. Расположим вершины графа по этажам (уровням, ярусам) так, чтобы корень находился в верхнем нулевом этаже, смежные с ним вершины занимали следующий нижний первый этаж, смежные с вершинами /с-го этажа занимали А:+1-й этаж (который ниже, чем ^-й этаж) и т.д. После установления вершин по этажам начинаем процедуру обхода вершин. Обход графа по глубине. При таком обходе после очередной рассмотренной вершины к-то этажа выбирается сменшая с ней вершина следующего k+1-ro этажа. Если очередная рассмотренная вершина висячая и её достижение не даёт желаемого решения задачи, то возвращаются до ближайшей вершины, откуда можно пройти до новой непросмотренной вершины и т. д. Обход графа по ширине. При этом просмотр вершин дерева ведётся по этажам (начиная с корня дерева). Переход от вершин ^-го этажа к вершинам следующего k-^l-ro этажа производится только после просмотра всех вершин к-то этажа. При компьютерной реализации обходов дерева (по глубине или ширине) целесообразно использовать задание графа с помощью списков смежностей вершин. Отметим, что d приведённом описании номера этажей растут сверху вниз. В некоторых случаях нижний эталс считается нулевым и при движении вверх номера этяжей возрастают.
Made with FlippingBook
RkJQdWJsaXNoZXIy MTY0OTYy