Страница 45 номер 68, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Является ли в графе октаэдра (рис. 28, \(в\)) цепью путь: а) \(MDABN\); б) \(BMCDMAN\)?
Цепь — путь без повторяющихся вершин. Рёбра графа октаэдра: \(MA\), \(MB\), \(MC\), \(MD\), \(NA\), \(NB\), \(NC\), \(ND\), \(AB\), \(BC\), \(CD\), \(DA\).
а) Последовательность \(MDABN\): соседние пары \(MD\), \(DA\), \(AB\), \(BN\) — рёбра графа, значит, это путь длины 4; вершины \(M\), \(D\), \(A\), \(B\), \(N\) попарно различны. Этот путь является цепью.
б) Последовательность \(BMCDMAN\): соседние пары \(BM\), \(MC\), \(CD\), \(DM\), \(MA\), \(AN\) — рёбра графа, значит, это путь длины 6; но вершина \(M\) стоит в нём и на втором, и на пятом месте. Путь с повторяющейся вершиной цепью не является.
Ответ: а) да, \(MDABN\) — цепь; б) нет, \(BMCDMAN\) цепью не является: это путь, в котором вершина \(M\) встречается дважды.
Является ли в графе октаэдра (рис. 28, \(в\)) цепью путь: а) \(MDABN\); б) \(BMCDMAN\)?
Цепь — это путь без повторяющихся вершин. Значит, проверять надо две вещи: во-первых, что каждые две соседние вершины последовательности соединены ребром (иначе перед нами и не путь), во-вторых, что ни одна вершина не встречается дважды.
Рёбра графа октаэдра: \(MA\), \(MB\), \(MC\), \(MD\), \(NA\), \(NB\), \(NC\), \(ND\), \(AB\), \(BC\), \(CD\), \(DA\). Не соединены только пары \(M\) и \(N\), \(A\) и \(C\), \(B\) и \(D\).
а) Последовательность \(MDABN\). Соседние пары: \(MD\) — такое ребро есть, \(DA\) — есть, \(AB\) — есть, \(BN\) — есть. Значит, \(MDABN\) — путь длины 4. Вершины \(M\), \(D\), \(A\), \(B\), \(N\) попарно различны, повторов нет. Значит, этот путь является цепью.
б) Последовательность \(BMCDMAN\). Соседние пары: \(BM\), \(MC\), \(CD\), \(DM\), \(MA\), \(AN\) — все шесть являются рёбрами графа, значит, \(BMCDMAN\) — путь длины 6. Но вершина \(M\) стоит в нём и на втором, и на пятом месте, то есть повторяется. Путь с повторяющейся вершиной цепью не является.
Ответ: а) да, \(MDABN\) — цепь; б) нет, \(BMCDMAN\) цепью не является: это путь, в котором вершина \(M\) встречается дважды.
