ГДЗ: Упражнение 85 - § 4 (Виды графов) - (Вероятность и статистика 10 класс, Бунимович Евгений Абрамович, Булычев Владимир Александрович)

Граф называется связным, если для любых двух его вершин найдётся путь, который их соединяет. Несвязный граф состоит из нескольких связных компонент (компонент связности). Граф без рёбер — «самый несвязный»: каждая вершина — отдельная компонента. Полный граф — граф, в котором каждая пара вершин соединена ребром; он связен и содержит наибольшее возможное число рёбер.

Ребро связного графа называется мостом, если после его удаления граф становится несвязным. Ребро является мостом тогда и только тогда, когда оно не принадлежит ни одному циклу: если ребро входит в цикл, после его удаления вершины по-прежнему связаны другой частью цикла.

Дерево — связный граф без циклов. Свойства: 1) в дереве каждое ребро является мостом; 2) между любыми двумя вершинами дерева существует единственная цепь; 3) дерево из \( n \) вершин содержит ровно \( n - 1 \) ребро; 4) в дереве с двумя и более вершинами есть хотя бы две вершины степени 1. Дерево, полученное из связного графа вычёркиванием «лишних» рёбер (по одному из каждого цикла), называется остовным деревом (остовом, каркасом) графа.

Если в дереве выделена особая вершина — корень, дерево называют корневым и рисуют по ярусам: корень выше всех, ниже — его соседи и т. д. Вершины степени 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 \).