Элементы теории графов. Сюсюкалов А.И - 32 стр.

UptoLike

ВУЗ: 

РГРТУ | Рязань

Составители: 

Рубрика: 

27
выходят из одной точки; б) да. Например, 3 улицы образуют
правильный треугольник и еще 3 улицы соединяют центр тре-
угольника с его вершинами. 8. Граф связен, степени его вершин
четны.
3. 1. Рассмотрим произвольную компоненту связности этого
графа. Она не является деревом, так как в ней нет висячей вер-
шины. Значит, в ней есть цикл. 2. Из условия граф страны – де-
рево. У него есть висячая вершина. Удалим ее и выходящее из
нее ребро. Оставшийся граф также дерево. У него есть висячая
вершина, которую также удалим и так далее. Проделав эту опе-
рацию
1
n
раз, получим граф, состоящий из одной вершины.
Так как удалялось по одному ребру, то вначале их было
1
n
.
3. Будем рассматривать волейбольную сетку как граф, верши-
нами которого являются узлы сетки, а ребрами – веревочки. В
этом графе нужно удалить как можно больше ребер так, чтобы
он остался связным. Заметим, что пока в графе есть цикл, воз-
можно удаление любого ребра этого цикла. Связный граф, не
имеющий циклов, является деревом. Поэтому, только получив
дерево, мы не сможем убрать ни одного ребра. Изначально в
графе было
606505160050601
ребер и
3065160151
вершин, то есть дерево будет иметь
30650
ребер. Таким обра-
зом, разрезать можно
300003065060650
веревочек.
4. 40629
2
29
30 . 5. а), б) Рассмотреть «максимальное» де-
рево и выбрать путь, соединяющий две висячие вершины. 6.
63
.
Поставим внутри каждого квадратика
1
1
точку и, убирая
спичку, соединим соответствующие точки. Тогда мы получим
связный граф, а минимальное число ребер у связного графа в
том случае, когда граф – дерево. Так как вершин 64, то число
ребер не меньше 63.
4. 1. 4. 2. Пусть отмеченные точки и вершины квадрата –
вершины, а соединяющие их отрезки и стороны квадрата – реб-
ра плоского графа. Для каждого куска, на которые граф разби-
вает плоскость, посчитаем число ограничивающих ребер и все
полученные числа сложим. Поскольку каждое ребро разделяет

Страницы