Страница 48 номер 72, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни

На чертеже графа 1 не пропечатаны два горизонтальных ребра: каждая левая вершина соединена с каждой правой.

Вершины буквами не обозначены, поэтому обозначим их сами.

В графе 1 вершины стоят двумя столбцами: \(A_1\), \(B_1\), \(C_1\) — левый столбец сверху вниз, \(D_1\), \(E_1\), \(F_1\) — правый столбец сверху вниз.

В графе 2: \(A_2\) — верхняя вершина, \(D_2\) — внутренняя вершина под ней, \(B_2\) и \(C_2\) — внутренние левая и правая, \(E_2\) и \(F_2\) — нижние левая и правая.

В графе 3: \(A_3\), \(B_3\), \(C_3\) — вершины внешнего треугольника (верхняя, нижняя левая, нижняя правая), \(D_3\), \(E_3\), \(F_3\) — вершины внутреннего треугольника (верхняя, левая, правая); соединяющие рёбра идут от \(A_3\) к \(D_3\), от \(B_3\) к \(E_3\), от \(C_3\) к \(F_3\).

В графе 4: \(A_4\) — верхняя вершина, \(B_4\) — левая, \(C_4\) — средняя, \(D_4\) — правая верхняя, \(E_4\) — нижняя, \(F_4\) — правая нижняя.

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

Рёбра графа 1: \(A_1D_1\), \(A_1E_1\), \(A_1F_1\), \(B_1D_1\), \(B_1E_1\), \(B_1F_1\), \(C_1D_1\), \(C_1E_1\), \(C_1F_1\). Вершины разбиваются на две тройки — \(\{A_1,\ B_1,\ C_1\}\) и \(\{D_1,\ E_1,\ F_1\}\); каждая вершина первой тройки соединена с каждой вершиной второй, а внутри троек рёбер нет.

Рёбра графа 2: \(A_2D_2\), \(A_2E_2\), \(A_2F_2\), \(B_2D_2\), \(B_2E_2\), \(B_2F_2\), \(C_2D_2\), \(C_2E_2\), \(C_2F_2\). Здесь тоже две тройки — \(\{A_2,\ B_2,\ C_2\}\) и \(\{D_2,\ E_2,\ F_2\}\), каждая вершина одной тройки соединена с каждой вершиной другой, и внутри троек рёбер нет.

Сопоставим вершины с одинаковыми буквами: \(A_1 \leftrightarrow A_2\), \(B_1 \leftrightarrow B_2\), \(C_1 \leftrightarrow C_2\), \(D_1 \leftrightarrow D_2\), \(E_1 \leftrightarrow E_2\), \(F_1 \leftrightarrow F_2\). Соответствие взаимно однозначно, а списки рёбер записаны одними и теми же парами букв. Значит, каждому ребру графа 1 отвечает ребро графа 2 с соответствующими концами, и наоборот, то есть графы 1 и 2 изоморфны.

Рёбра графа 3: \(A_3B_3\), \(B_3C_3\), \(C_3A_3\) (внешний треугольник), \(D_3E_3\), \(E_3F_3\), \(F_3D_3\) (внутренний треугольник), \(A_3D_3\), \(B_3E_3\), \(C_3F_3\) (соединяющие рёбра).

Рёбра графа 4: \(A_4B_4\), \(B_4C_4\), \(C_4A_4\) (первый треугольник), \(D_4E_4\), \(E_4F_4\), \(F_4D_4\) (второй треугольник), \(A_4D_4\), \(B_4E_4\), \(C_4F_4\) (соединяющие рёбра).

Сопоставим и здесь вершины с одинаковыми буквами: \(A_3 \leftrightarrow A_4\), \(B_3 \leftrightarrow B_4\), \(C_3 \leftrightarrow C_4\), \(D_3 \leftrightarrow D_4\), \(E_3 \leftrightarrow E_4\), \(F_3 \leftrightarrow F_4\). Списки рёбер снова записаны одними и теми же парами букв, поэтому графы 3 и 4 изоморфны.

Осталось проверить, что графы первой пары не изоморфны графам второй.

В графе 3 есть три вершины, попарно соединённые рёбрами: \(A_3\), \(B_3\), \(C_3\). То же верно и для графа 4: это \(A_4\), \(B_4\), \(C_4\).

В графе 1 таких трёх вершин нет. Концы каждого ребра лежат в разных тройках, а из любых трёх вершин какие-то две попадут в одну тройку — и ребром они не соединены. То же рассуждение годится и для графа 2.

При изоморфизме трём попарно соединённым вершинам отвечают три вершины, тоже попарно соединённые: каждому из трёх рёбер отвечает ребро с соответствующими концами. Поэтому ни граф 1, ни граф 2 не изоморфен ни графу 3, ни графу 4.

Ответ: изоморфны графы 1 и 2, а также графы 3 и 4; других пар изоморфных графов здесь нет.