Из ящика, в котором лежат две одинаковые пары перчаток, одну за другой достают три перчатки. Нарисуйте дерево этого эксперимента. Сколько листьев у этого дерева? Сколько равновозможных исходов у этого эксперимента?
Нарисуйте дерево, найдите число листьев и число равновозможных исходов.
Ответ
В ящике 4 перчатки: две левые \( Л_1, Л_2 \) и две правые \( П_1, П_2 \). Достают три перчатки по очереди. Из корня выходят 4 ребра (первая перчатка), из каждой вершины первого яруса — 3 ребра (вторая перчатка из трёх оставшихся), из каждой вершины второго яруса — 2 ребра (третья перчатка из двух оставшихся).
Листьев \( 4 \cdot 3 \cdot 2 = 24 \), и все они равновозможны, так как на каждом шаге любая из оставшихся перчаток попадается с одинаковыми шансами. Вероятность каждого исхода \( \dfrac{1}{24} \).
Если различать только «левая — правая», у дерева 6 листьев: ЛЛП, ЛПЛ, ЛПП, ПЛЛ, ПЛП, ППЛ (трёх одинаковых подряд быть не может — перчаток каждого вида только две); эти исходы тоже оказываются равновозможными, по 4 «подробных» исхода в каждом, но обосновать это можно только с помощью полного дерева.
Ответ: 24 листа, 24 равновозможных исхода.
Что применять при решении
Связный граф, компоненты связности, полный граф
Граф называется связным, если для любых двух его вершин найдётся путь, который их соединяет. Несвязный граф состоит из нескольких связных компонент (компонент связности). Граф без рёбер — «самый несвязный»: каждая вершина — отдельная компонента. Полный граф — граф, в котором каждая пара вершин соединена ребром; он связен и содержит наибольшее возможное число рёбер.
Число рёбер полного графа с \( 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. Оплата после того, как увидите работу.
Уведомление об авторском праве и цитировании
ВНИМАНИЕ: Представленные фрагменты из учебных материалов
используются исключительно в научно-образовательных целях в объеме,
оправданном поставленной целью.
Данное использование осуществляется в рамках, установленных законодательством об авторском праве
(в частности, нормами о свободном использовании произведения для образовательных целей).
В соответствии с законодательством, автор и источник заимствования
указаны для каждого используемого фрагмента.
