Страница 59 номер 97, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
В дереве 1001 вершина. Может ли быть так, что: а) длина любой цепи в этом дереве не больше 1; б) длина любой цепи в этом дереве не больше 2; в) в этом дереве найдётся цепь длиной 1000?
Рёбер в дереве \(1001 - 1 = 1000\), сумма степеней всех вершин \(2 \cdot 1000 = 2000\). Длина цепи — число её рёбер.
а) Нет. Сумма степеней равна 2000, а вершин 1001, поэтому не все степени равны 1: найдётся вершина \(B\) степени не меньше 2. Ни петель, ни кратных рёбер в дереве нет, потому что петля — цикл длины 1, а пара кратных рёбер — цикл длины 2. Значит, два ребра при вершине \(B\) ведут в две различные вершины \(A\) и \(C\), и \(ABC\) — цепь длины 2, которая длиннее 1.
б) Да. Звезда: вершина \(A\) соединена ребром с каждой из 1000 остальных вершин. Это дерево — граф связен, в нём 1000 рёбер и нет циклов, потому что каждое ребро содержит вершину \(A\), а в цикле вершины не повторяются. Каждое ребро звезды содержит вершину \(A\), а в цепи вершина \(A\) стоит не больше одного раза и примыкает не больше чем к двум её рёбрам, поэтому в цепи не больше двух рёбер.
в) Да. Цепь \(V_1V_2\ldots V_{1001}\), в которой ребро соединяет вершины с соседними номерами, — дерево, и оно само является цепью с 1000 рёбер, то есть цепью длины 1000.
Ответ: а) нет, в дереве с 1001 вершиной обязательно найдётся цепь длины 2; б) да, так бывает — например, у звезды, одна вершина которой соединена с каждой из 1000 остальных; в) да, так бывает — например, у цепи из 1001 вершины: её длина равна 1000.
В дереве 1001 вершина. Может ли быть так, что: а) длина любой цепи в этом дереве не больше 1; б) длина любой цепи в этом дереве не больше 2; в) в этом дереве найдётся цепь длиной 1000?
В конечном дереве вершин на одну больше, чем рёбер, поэтому рёбер в нём \(1001 - 1 = 1000\), а сумма степеней всех вершин равна \(2 \cdot 1000 = 2000\). Длина цепи — это число её рёбер.
а) Нет, так быть не может. Сумма степеней равна 2000, а вершин 1001, поэтому не все степени равны 1: найдётся вершина \(B\) степени не меньше 2. В дереве нет ни петель, ни кратных рёбер, потому что петля — это цикл длины 1, а пара кратных рёбер — цикл длины 2. Значит, два ребра при вершине \(B\) ведут в две различные вершины \(A\) и \(C\), и \(ABC\) — цепь длины 2: её вершины различны, а соседние соединены рёбрами. Такая цепь длиннее 1, поэтому не может быть, чтобы длина любой цепи была не больше 1.
б) Да, так может быть. Возьмём звезду: вершина \(A\) соединена ребром с каждой из 1000 остальных вершин. Это дерево: граф связен, в нём 1000 рёбер и нет циклов, потому что каждое ребро содержит вершину \(A\), а в цикле вершины не повторяются.
Каждое ребро звезды содержит вершину \(A\). В цепи вершины не повторяются, поэтому вершина \(A\) стоит в ней не больше одного раза и примыкает не больше чем к двум её рёбрам. Значит, в цепи не больше двух рёбер, то есть длина любой цепи не больше 2.
в) Да, так может быть. Возьмём цепь \(V_1V_2\ldots V_{1001}\), в которой ребро соединяет вершины с соседними номерами. Это дерево, и оно само является цепью с 1000 рёбер, то есть цепью длины 1000.
Ответ: а) нет, в дереве с 1001 вершиной обязательно найдётся цепь длины 2; б) да, так бывает — например, у звезды, одна вершина которой соединена с каждой из 1000 остальных; в) да, так бывает — например, у цепи из 1001 вершины: её длина равна 1000.
