Страница 45 номер 69, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Является ли в графе октаэдра (см. рис. 28, \(в\)) циклом путь: а) \(ABCDA\); б) \(ABMCDMA\)?
В цикле каждые две соседние вершины записи соединены ребром, начало и конец совпадают, а других повторов в записи нет.
Рёбра графа октаэдра: \(MA\), \(MB\), \(MC\), \(MD\), \(NA\), \(NB\), \(NC\), \(ND\), \(AB\), \(BC\), \(CD\), \(DA\).
а) Последовательность \(ABCDA\): соседние пары \(AB\), \(BC\), \(CD\), \(DA\) — рёбра графа, начало и конец совпали, а вершины \(A\), \(B\), \(C\), \(D\) попарно различны. Значит, \(ABCDA\) — цикл длины 4.
б) Последовательность \(ABMCDMA\): соседние пары \(AB\), \(BM\), \(MC\), \(CD\), \(DM\), \(MA\) — рёбра графа, начало и конец совпали, то есть это замкнутый путь длины 6. Но вершина \(M\) стоит в нём и на третьем, и на шестом месте, а в цикле повторяться может только начальная вершина. Циклом эта последовательность не является.
Ответ: а) да, \(ABCDA\) — цикл длины 4; б) нет, \(ABMCDMA\) циклом не является: это замкнутый путь, в котором вершина \(M\) встречается дважды.
Является ли в графе октаэдра (см. рис. 28, \(в\)) циклом путь: а) \(ABCDA\); б) \(ABMCDMA\)?
Циклом длины \(n\) называется граф на вершинах \(V_1\), \(V_2\), ..., \(V_n\) с рёбрами \(V_1V_2\), \(V_2V_3\), ..., \(V_{n-1}V_n\), \(V_nV_1\). Записывают цикл цепочкой вершин, в конце которой повторена первая вершина, причём сами вершины \(V_1\), \(V_2\), ..., \(V_n\) попарно различны. Значит, проверять надо три вещи: что каждые две соседние вершины записи соединены ребром, что начало и конец совпали и что других повторов в записи нет.
Рёбра графа октаэдра: \(MA\), \(MB\), \(MC\), \(MD\), \(NA\), \(NB\), \(NC\), \(ND\), \(AB\), \(BC\), \(CD\), \(DA\). Не соединены только пары \(M\) и \(N\), \(A\) и \(C\), \(B\) и \(D\).
а) Последовательность \(ABCDA\). Соседние пары: \(AB\), \(BC\), \(CD\), \(DA\) — все четыре являются рёбрами графа. Начало и конец совпали, а вершины \(A\), \(B\), \(C\), \(D\) попарно различны и других повторов нет. Значит, \(ABCDA\) — цикл длины 4.
б) Последовательность \(ABMCDMA\). Соседние пары: \(AB\), \(BM\), \(MC\), \(CD\), \(DM\), \(MA\) — все шесть являются рёбрами графа, а начало и конец совпали, так что это замкнутый путь длины 6. Но вершина \(M\) стоит в нём и на третьем, и на шестом месте, то есть повторяется, а в цикле повторяться может только начальная вершина. Значит, циклом эта последовательность не является.
Ответ: а) да, \(ABCDA\) — цикл длины 4; б) нет, \(ABMCDMA\) циклом не является: это замкнутый путь, в котором вершина \(M\) встречается дважды.
