Страница 48 номер 71, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Докажите, что два графа, изображённые на рисунке 35, изоморфны.
В первом графе четыре вершины \(A\), \(B\), \(C\), \(D\) и четыре ребра \(AD\), \(DC\), \(AC\), \(BC\); во втором — четыре вершины \(K\), \(L\), \(M\), \(N\) и четыре ребра \(KL\), \(LM\), \(MN\), \(LN\). Вершин поровну и рёбер поровну.
Соответствие вершин: \[B \leftrightarrow K,\quad C \leftrightarrow L,\quad D \leftrightarrow M,\quad A \leftrightarrow N.\]
Каждой вершине первого графа отвечает ровно одна вершина второго и наоборот, поэтому соответствие взаимно однозначно. Каждому ребру первого графа отвечает пара вершин второго:
\(BC \leftrightarrow KL\) — ребро второго графа;
\(AC \leftrightarrow NL\) — ребро второго графа;
\(DC \leftrightarrow ML\) — ребро второго графа;
\(AD \leftrightarrow NM\) — ребро второго графа.
Четыре ребра первого графа перешли в четыре различных ребра второго, а других рёбер во втором графе нет, значит, соответствие рёбер тоже взаимно однозначно. Оба условия определения выполнены, графы изоморфны.
Ответ: графы изоморфны; соответствие вершин \(B \leftrightarrow K\), \(C \leftrightarrow L\), \(D \leftrightarrow M\), \(A \leftrightarrow N\) переводит каждое ребро первого графа в ребро второго.
Докажите, что два графа, изображённые на рисунке 35, изоморфны.
В первом графе четыре вершины \(A\), \(B\), \(C\), \(D\) и четыре ребра: \(AD\), \(DC\), \(AC\), \(BC\). Во втором графе тоже четыре вершины \(K\), \(L\), \(M\), \(N\) и четыре ребра: \(KL\), \(LM\), \(MN\), \(LN\). Значит, первое условие изоморфизма выполнено: вершин поровну и рёбер поровну.
Установим соответствие вершин: \[B \leftrightarrow K,\quad C \leftrightarrow L,\quad D \leftrightarrow M,\quad A \leftrightarrow N.\]
Каждой вершине первого графа отвечает ровно одна вершина второго и наоборот, поэтому соответствие взаимно однозначно.
Каждому ребру первого графа сопоставим ту пару вершин второго, которая отвечает его концам:
\(BC \leftrightarrow KL\) — ребро второго графа;
\(AC \leftrightarrow NL\) — ребро второго графа;
\(DC \leftrightarrow ML\) — ребро второго графа;
\(AD \leftrightarrow NM\) — ребро второго графа.
Четыре ребра первого графа перешли в четыре различных ребра второго графа, а других рёбер во втором графе нет. Значит, соответствие рёбер тоже взаимно однозначно, и ребро связывает две вершины первого графа тогда и только тогда, когда соответствующее ребро связывает соответствующие вершины второго графа.
Оба условия определения выполнены, следовательно, графы изоморфны.
Ответ: графы изоморфны; соответствие вершин \(B \leftrightarrow K\), \(C \leftrightarrow L\), \(D \leftrightarrow M\), \(A \leftrightarrow N\) переводит каждое ребро первого графа в ребро второго.
