Страница 49 номер 73, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Даны два неизоморфных графа (рис. 37). В каждом 5 вершин и 8 рёбер. Удалите из этих графов по одному ребру так, чтобы получились изоморфные подграфы этих графов.
В первом графе пять вершин \(A\), \(B\), \(C\), \(D\), \(E\) и восемь рёбер: \(AB\), \(AE\), \(ED\), \(BD\), \(AD\), \(BE\), \(BC\), \(CD\). Во втором — пять вершин \(J\), \(K\), \(L\), \(M\), \(N\) и восемь рёбер: \(JK\), \(JL\), \(JM\), \(JN\), \(KL\), \(KN\), \(LM\), \(NM\).
Удалим из первого графа ребро \(AD\), а из второго — ребро \(KN\): в каждом подграфе останется по пять вершин и по семь рёбер:
в первом — \(AB\), \(AE\), \(BE\), \(BD\), \(BC\), \(CD\), \(ED\);
во втором — \(JK\), \(JL\), \(JM\), \(JN\), \(KL\), \(LM\), \(NM\).
Соответствие вершин: \[B \leftrightarrow J,\quad A \leftrightarrow K,\quad E \leftrightarrow L,\quad D \leftrightarrow M,\quad C \leftrightarrow N.\]
Оно взаимно однозначно. Каждому ребру первого подграфа отвечает пара вершин второго:
\(AB \leftrightarrow KJ\) — ребро второго подграфа;
\(AE \leftrightarrow KL\) — ребро второго подграфа;
\(BE \leftrightarrow JL\) — ребро второго подграфа;
\(BD \leftrightarrow JM\) — ребро второго подграфа;
\(BC \leftrightarrow JN\) — ребро второго подграфа;
\(CD \leftrightarrow NM\) — ребро второго подграфа;
\(ED \leftrightarrow LM\) — ребро второго подграфа.
Семь рёбер первого подграфа перешли в семь различных рёбер второго, а других рёбер во втором подграфе нет, значит, соответствие рёбер тоже взаимно однозначно. Оба условия определения выполнены, подграфы изоморфны.
Ответ: достаточно удалить ребро \(AD\) из первого графа и ребро \(KN\) из второго; при соответствии \(B \leftrightarrow J\), \(A \leftrightarrow K\), \(E \leftrightarrow L\), \(D \leftrightarrow M\), \(C \leftrightarrow N\) полученные подграфы изоморфны.
Даны два неизоморфных графа (рис. 37). В каждом 5 вершин и 8 рёбер. Удалите из этих графов по одному ребру так, чтобы получились изоморфные подграфы этих графов.
В первом графе пять вершин \(A\), \(B\), \(C\), \(D\), \(E\) и восемь рёбер: \(AB\), \(AE\), \(ED\), \(BD\), \(AD\), \(BE\), \(BC\), \(CD\).
Во втором графе пять вершин \(J\), \(K\), \(L\), \(M\), \(N\) и восемь рёбер: \(JK\), \(JL\), \(JM\), \(JN\), \(KL\), \(KN\), \(LM\), \(NM\).
Удалим из первого графа ребро \(AD\), а из второго — ребро \(KN\). В каждом подграфе останется по пять вершин и по семь рёбер:
в первом — \(AB\), \(AE\), \(BE\), \(BD\), \(BC\), \(CD\), \(ED\);
во втором — \(JK\), \(JL\), \(JM\), \(JN\), \(KL\), \(LM\), \(NM\).
Установим соответствие вершин: \[B \leftrightarrow J,\quad A \leftrightarrow K,\quad E \leftrightarrow L,\quad D \leftrightarrow M,\quad C \leftrightarrow N.\]
Оно взаимно однозначно. Сопоставим каждому ребру первого подграфа пару соответствующих вершин второго:
\(AB \leftrightarrow KJ\) — ребро второго подграфа;
\(AE \leftrightarrow KL\) — ребро второго подграфа;
\(BE \leftrightarrow JL\) — ребро второго подграфа;
\(BD \leftrightarrow JM\) — ребро второго подграфа;
\(BC \leftrightarrow JN\) — ребро второго подграфа;
\(CD \leftrightarrow NM\) — ребро второго подграфа;
\(ED \leftrightarrow LM\) — ребро второго подграфа.
Семь рёбер первого подграфа перешли в семь различных рёбер второго, а других рёбер во втором подграфе нет. Значит, соответствие рёбер тоже взаимно однозначно и ребро связывает две вершины первого подграфа тогда и только тогда, когда соответствующее ребро связывает соответствующие вершины второго. Оба условия определения выполнены, подграфы изоморфны.
Оба подграфа удобно нарисовать одинаково: вершина, из которой выходят четыре ребра, — в середине, а остальные четыре вершины — дугой над ней, соединённые подряд.
Ответ: достаточно удалить ребро \(AD\) из первого графа и ребро \(KN\) из второго; при соответствии \(B \leftrightarrow J\), \(A \leftrightarrow K\), \(E \leftrightarrow L\), \(D \leftrightarrow M\), \(C \leftrightarrow N\) полученные подграфы изоморфны.
