Страница 58 номер 94, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Приведите пример бесконечного дерева, в котором: а) только одна концевая вершина; б) бесконечно много концевых вершин.
а) Луч: вершины \(V_1\), \(V_2\), \(V_3\), \(\ldots\) занумерованы всеми натуральными числами, ребро соединяет две вершины, номера которых отличаются на 1.
Граф связен: от вершины \(V_k\) до вершины \(V_m\) ведёт цепь по всем промежуточным номерам. Циклов нет: в цикле конечное число вершин, среди них есть вершина \(V_m\) с наибольшим номером, и к ней в цикле должны примыкать два ребра, а второе её ребро \(V_mV_{m+1}\) ведёт в вершину с бо́льшим номером, которой в цикле нет. Значит, это дерево.
Степень вершины \(V_1\) равна 1, а степень каждой из остальных вершин \(V_n\) равна 2, потому что к ней примыкают рёбра \(V_{n-1}V_n\) и \(V_nV_{n+1}\). Концевая вершина ровно одна.
б) «Гребёнка»: тот же луч, но к каждой его вершине \(V_n\) примыкает ещё одно ребро \(V_nU_n\), ведущее в новую вершину \(U_n\).
Граф связен: от любой вершины \(U_n\) ребро ведёт в \(V_n\), а вершины луча связаны между собой. Циклов нет: каждая вершина \(U_n\) имеет степень 1 и в цикл войти не может, а без них остаётся тот же луч.
Значит, это дерево, и каждая из вершин \(U_1\), \(U_2\), \(U_3\), \(\ldots\) — концевая; таких вершин бесконечно много.
Ответ: а) луч — вершины \(V_1\), \(V_2\), \(V_3\), \(\ldots\), в котором ребром соединены вершины с соседними номерами: у него единственная концевая вершина \(V_1\); б) «гребёнка» — тот же луч, к каждой вершине которого примыкает ещё по одному ребру с новым концом: у неё бесконечно много концевых вершин.
Приведите пример бесконечного дерева, в котором: а) только одна концевая вершина; б) бесконечно много концевых вершин.
а) Возьмём луч: вершины \(V_1\), \(V_2\), \(V_3\), \(\ldots\) занумерованы всеми натуральными числами, а ребро соединяет две вершины, номера которых отличаются на 1.
Этот граф связен: от вершины \(V_k\) до вершины \(V_m\) ведёт цепь по всем промежуточным номерам. Циклов в нём нет: в цикле конечное число вершин, среди них есть вершина \(V_m\) с наибольшим номером, и к ней в цикле должны примыкать два ребра, а второе её ребро \(V_mV_{m+1}\) ведёт в вершину с бо́льшим номером, которой в цикле нет. Значит, это дерево.
Степень вершины \(V_1\) равна 1 — это концевая вершина. Степень каждой из остальных вершин \(V_n\) равна 2, потому что к ней примыкают рёбра \(V_{n-1}V_n\) и \(V_nV_{n+1}\). Значит, концевая вершина ровно одна.
б) Возьмём «гребёнку»: тот же луч \(V_1\), \(V_2\), \(V_3\), \(\ldots\), но к каждой его вершине \(V_n\) примыкает ещё одно ребро \(V_nU_n\), ведущее в новую вершину \(U_n\).
Этот граф связен: от любой вершины \(U_n\) ребро ведёт в \(V_n\), а вершины луча связаны между собой. Циклов нет: каждая вершина \(U_n\) имеет степень 1 и в цикл войти не может, а без них остаётся тот же луч, в котором циклов нет.
Значит, это дерево, и каждая из вершин \(U_1\), \(U_2\), \(U_3\), \(\ldots\) — концевая. Таких вершин бесконечно много.
Ответ: а) луч — вершины \(V_1\), \(V_2\), \(V_3\), \(\ldots\), в котором ребром соединены вершины с соседними номерами: у него единственная концевая вершина \(V_1\); б) «гребёнка» — тот же луч, к каждой вершине которого примыкает ещё по одному ребру с новым концом: у неё бесконечно много концевых вершин.
