16A. Деревья

Шесть компьютеров стоят в кабинете, и ни один ни с одним не соединён. Каждый день системный администратор соединяет кабелем какие-нибудь два. Автономной зоной назовём набор компьютеров, между любыми двумя из которых можно передать данные — напрямую или через другие компьютеры, — и такой, что ни с одним компьютером снаружи обмена нет. а) Как может измениться число автономных зон за один день? б) Какого наименьшего числа кабелей хватит, чтобы все шесть компьютеров оказались в одной зоне?

Из спичек длины 1 сложена клетчатая доска 8 × 8. Жук хочет, чтобы с любой клетки он мог доползти до любой другой, не переползая через спички. Какое наименьшее число спичек придётся убрать?

Даны восемь камней, все разного веса. Есть весы, позволяющие сравнить по весу любые два камня. Какое наименьшее число взвешиваний нужно, чтобы наверняка найти самый тяжёлый камень?

Сколько рёбер куба максимум можно перекусить посередине, чтобы он не распался на части?

Волейбольная сетка имеет вид прямоугольника 3 × 5 клеток. Какое наибольшее число верёвочек можно перерезать, чтобы сетка не распалась на куски?

В классе 20 человек. Компанией назовём набор ребят, любые двое из которых связаны цепочкой знакомств внутри этого набора и который ни с кем снаружи не знаком. а) В классе ровно 16 пар знакомых. На какое наименьшее число компаний может разбиться класс? б) Класс разбился ровно на четыре компании. Какое наименьшее число пар знакомых в нём?

Дан граф с n вершинами. Докажите, что а) если граф связен, то в нём не менее n − 1 ребра; б) если граф распадается на k компонент связности, то в нём не менее n − k рёбер; в) если в связном графе есть цикл, то любое ребро этого цикла можно удалить (концы остаются на месте), и граф останется связным.

Пусть граф связен. Докажите, что следующие свойства равносильны: • в графе нет циклов; • при удалении любого ребра граф перестаёт быть связным; • рёбер на одно меньше, чем вершин. Граф, обладающий этими свойствами, называется деревом.

Два графа называют изоморфными, если вершины одного можно занумеровать вершинами другого так, что рёбра перейдут в рёбра. Сколько существует попарно неизоморфных деревьев на шести вершинах? Нарисуйте их все.

а) В связном графе 9 вершин и 14 рёбер. Какое наименьшее число рёбер надо удалить, чтобы в графе не осталось ни одного цикла? б) Докажите, что из любого связного графа можно выкинуть часть рёбер так, чтобы получилось дерево с теми же вершинами. Такое дерево называют остовом исходного графа.

Вершину степени 1 называют висячей, или листом. а) Докажите, что в дереве больше чем с одной вершиной есть висячая вершина. (идите по рёбрам, каждый раз выбирая то, по которому ещё не шли) б) Докажите, что таких вершин хотя бы две. в) Сколько висячих вершин может быть у дерева с n вершинами?

Система станций метро устроена так, что из каждой станции можно проехать в каждую. Докажите, что одну из станций можно закрыть, запретив проезжать через неё, так, что это свойство сохранится для оставшихся.

N -угольник разбит на треугольники несколькими диагоналями, не пересекающимися нигде, кроме вершин. Построим граф, соответствующий этому разбиению: отметим внутри каждого треугольника точку, соединяя две точки ребром ровно в том случае, когда соответствующие точкам треугольники имеют общую сторону . Докажите, что а) этот граф будет деревом; б) хотя бы у двух треугольников разбиения две стороны совпадают со сторонами N -угольника (если треугольников больше одного).