ГДЗ: § 4 / Виды графов / Вероятность и статистика 10 класс

Граф называется связным, если для любых двух его вершин найдётся хотя бы один путь, который их соединяет. Иначе граф несвязный и состоит из нескольких связных компонент.

Полный граф — граф, в котором каждая пара вершин соединена ребром. Полный граф с \( n \) вершинами содержит \( \dfrac{n(n-1)}{2} \) рёбер и, конечно, связен.

\( \dfrac{4 \cdot 3}{2} = 6 \) рёбер: четыре стороны четырёхугольника и две диагонали.

Ребро связного графа называется мостом, если после его удаления граф становится несвязным — распадается на две компоненты. Ребро является мостом тогда и только тогда, когда оно не входит ни в один цикл.

Деревом называется связный граф без циклов. Дерево можно понимать как связный граф без «лишних» рёбер: удаление любого ребра нарушает связность.

1) Каждое ребро дерева является мостом. 2) Между любыми двумя вершинами дерева существует единственная цепь. 3) Дерево с \( n \) вершинами содержит \( n - 1 \) ребро. 4) В любом дереве, где больше одной вершины, есть листья — вершины степени 1 (их не меньше двух). 5) Любое дерево планарно.

На единицу меньше, чем вершин: \( 2024 - 1 = 2023 \) ребра.

На единицу больше, чем рёбер: \( 1000 + 1 = 1001 \) вершина.

Дерево, в котором одна из вершин выбрана в качестве корня. Его рисуют по ярусам: корень — выше всех, на ярус ниже — соседи корня, ещё ниже — соседи этих соседей и т. д., как будто дерево подняли за корень и встряхнули. Пример — дерево вложенных папок на диске компьютера с корневой папкой наверху.

Конечные вершины дерева, имеющие степень 1. В дереве случайного эксперимента листья — это конечные состояния, то есть все возможные исходы эксперимента.

Корень — начало эксперимента (ещё ничего не произошло). Из корня проводят по ребру для каждого возможного результата первого этапа; из каждой полученной вершины — по ребру для каждого результата следующего этапа, и так до конца опыта. Вершины — состояния после очередного этапа (их удобно подписывать накопленной последовательностью результатов), рёбра — переходы между состояниями, листья — исходы всего эксперимента. Если опыт может закончиться раньше, соответствующая ветвь обрывается — листья оказываются на разных ярусах.

Пример: монету бросают два раза. Корень \( * \); из него два ребра «О» и «Р» в вершины О и Р; из каждой из них снова два ребра — получаем четыре листа: ОО, ОР, РО, РР — равновозможные исходы, вероятность каждого \( \dfrac14 \).

Другой пример: из коробки с одним белым и двумя чёрными шарами достают по одному шару, пока не появится белый. Корень; ребро «Б» в лист Б; ребро «Ч» в вершину Ч; из неё «Б» в лист ЧБ и «Ч» в вершину ЧЧ; из неё единственное ребро «Б» в лист ЧЧБ. Листья Б, ЧБ, ЧЧБ лежат на разных ярусах и не равновозможны.

Граф называется планарным, если его можно нарисовать на плоскости так, чтобы его рёбра попарно не пересекались (общие точки рёбер только в вершинах). Само такое изображение называется плоским графом.

Например, квадрат \( abcd \) с одной диагональю \( ac \): пять рёбер, никакие два не пересекаются. Или полный граф с четырьмя вершинами, нарисованный как треугольник \( abc \) с точкой \( d \) внутри, соединённой с \( a \), \( b \) и \( c \) (рис. 53, б учебника).

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

Да. Выберем любую вершину дерева корнем и будем рисовать вершины по ярусам, опуская каждый следующий ярус ниже и раздвигая вершины в стороны; рёбра идут только между соседними ярусами и не пересекаются. Значит, любое дерево можно изобразить без пересечения рёбер.

\( B - P + \Gamma = 2 \), где \( B \) — число вершин, \( P \) — число рёбер, \( \Gamma \) — число граней выпуклого многогранника.

Во всех случаях \( B - P + \Gamma = 2 \).

Если планарный граф нарисован без пересечений рёбер, плоскость разбивается на отдельные области — грани: любые две точки одной грани можно соединить кривой, не пересекающей рёбер, а точки разных граней — нельзя. Одна из граней всегда неограниченная (внешняя).

Для любого связного плоского графа \( B - P + \Gamma = 2 \), где \( B \) — число вершин, \( P \) — число рёбер, \( \Gamma \) — число граней (включая внешнюю).