Какое наименьшее и какое наибольшее количество листьев может иметь дерево, у которого 5 вершин? 50 вершин? 2024 вершины?
Найдите наименьшее и наибольшее число листьев дерева с 5, 50, 2024 вершинами.
Ответ
Наименьшее — 2. У дерева с \( n \ge 2 \) вершинами \( n - 1 \) ребро и сумма степеней \( 2n - 2 \). Если бы листьев было не больше одного, то сумма степеней была бы не меньше \( 1 + 2(n - 1) = 2n - 1 > 2n - 2 \). Значит, листьев хотя бы два, и ровно два листа у цепи (пути) \( v_1 - v_2 - \ldots - v_n \).
Наибольшее — \( n - 1 \). Все вершины листьями быть не могут: тогда сумма степеней равнялась бы \( n < 2n - 2 \) при \( n \ge 3 \). А \( n - 1 \) лист есть у звезды: одна центральная вершина, соединённая со всеми остальными.
Ответ: 5 вершин — от 2 до 4 листьев; 50 вершин — от 2 до 49; 2024 вершины — от 2 до 2023.
Что применять при решении
Связный граф, компоненты связности, полный граф
Граф называется связным, если для любых двух его вершин найдётся путь, который их соединяет. Несвязный граф состоит из нескольких связных компонент (компонент связности). Граф без рёбер — «самый несвязный»: каждая вершина — отдельная компонента. Полный граф — граф, в котором каждая пара вершин соединена ребром; он связен и содержит наибольшее возможное число рёбер.
Число рёбер полного графа с \( n \) вершинами: \( \dfrac{n(n-1)}{2} \)
Мосты
Ребро связного графа называется мостом, если после его удаления граф становится несвязным. Ребро является мостом тогда и только тогда, когда оно не принадлежит ни одному циклу: если ребро входит в цикл, после его удаления вершины по-прежнему связаны другой частью цикла.
Дерево и его свойства
Дерево — связный граф без циклов. Свойства: 1) в дереве каждое ребро является мостом; 2) между любыми двумя вершинами дерева существует единственная цепь; 3) дерево из \( n \) вершин содержит ровно \( n - 1 \) ребро; 4) в дереве с двумя и более вершинами есть хотя бы две вершины степени 1. Дерево, полученное из связного графа вычёркиванием «лишних» рёбер (по одному из каждого цикла), называется остовным деревом (остовом, каркасом) графа.
\( P = B - 1 \) для дерева с \( B \) вершинами и \( P \) рёбрами
Если в дереве выделена особая вершина — корень, дерево называют корневым и рисуют по ярусам: корень выше всех, ниже — его соседи и т. д. Вершины степени 1 называются листьями. Дерево случайного эксперимента: корень — начало опыта, вершины — состояния после очередного этапа, рёбра — переходы, листья — все возможные исходы. При \( n \) бросаниях монеты дерево двоичное и имеет \( 2^n \) листьев; у дерева опыта с кубиком из каждой вершины выходит по 6 рёбер. Если число шагов опыта разное (например, монету бросают до первого орла), листья лежат на разных ярусах и исходы не равновозможны.
Планарные графы и теорема Понтрягина — Куратовского
Граф называется планарным, если его можно нарисовать на плоскости так, чтобы рёбра попарно не пересекались (пересечения в вершинах не считаются); такое изображение называется плоским графом. Любое дерево планарно. Полный граф с 5 вершинами и граф «три домика — три колодца» (по три вершины в двух группах, каждая соединена с каждой из другой группы) непланарны. Теорема Понтрягина — Куратовского: любой непланарный граф содержит один из этих двух графов в качестве своей части.
Формула Эйлера для плоских графов и многогранников
Плоский граф разбивает плоскость на области — грани (одна из них неограниченная). Для любого связного плоского графа \( B - P + \Gamma = 2 \), где \( B \) — число вершин, \( P \) — рёбер, \( \Gamma \) — граней. Доказательство: для дерева \( P = B - 1 \), \( \Gamma = 1 \); удаление ребра из цикла уменьшает \( P \) и \( \Gamma \) на 1 и не меняет выражение. Та же формула верна для вершин, рёбер и граней выпуклого многогранника. Следствие: в планарном графе с \( B \ge 3 \) вершинами \( P \le 3B - 6 \).
Создать проектГотовый файл Word. Оплата после того, как увидите работу.
Уведомление об авторском праве и цитировании
ВНИМАНИЕ: Представленные фрагменты из учебных материалов
используются исключительно в научно-образовательных целях в объеме,
оправданном поставленной целью.
Данное использование осуществляется в рамках, установленных законодательством об авторском праве
(в частности, нормами о свободном использовании произведения для образовательных целей).
В соответствии с законодательством, автор и источник заимствования
указаны для каждого используемого фрагмента.
