Страница 54 номер 83, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Рассмотрите рисунок 28 на с. 45. Является ли эйлеровым: а) граф куба; б) граф тетраэдра; в) граф октаэдра?
Связный конечный граф является эйлеровым тогда и только тогда, когда в нём не больше двух вершин нечётной степени; все три графа связны.
а) В графе куба восемь вершин \(A\), \(B\), \(C\), \(D\), \(K\), \(L\), \(M\), \(N\) и 12 рёбер: \(AD\), \(DN\), \(NK\), \(KA\), \(BC\), \(CM\), \(ML\), \(LB\), \(AB\), \(DC\), \(NM\), \(KL\). Каждая вершина принадлежит ровно трём рёбрам, степени вершин: \(A\) — 3, \(B\) — 3, \(C\) — 3, \(D\) — 3, \(K\) — 3, \(L\) — 3, \(M\) — 3, \(N\) — 3. Вершин нечётной степени восемь, это больше двух, значит, граф куба не является эйлеровым.
б) В графе тетраэдра четыре вершины \(A\), \(B\), \(C\), \(D\) и 6 рёбер: \(AB\), \(AC\), \(AD\), \(BC\), \(BD\), \(CD\). Степени вершин: \(A\) — 3, \(B\) — 3, \(C\) — 3, \(D\) — 3. Вершин нечётной степени четыре, это больше двух, значит, граф тетраэдра не является эйлеровым.
в) В графе октаэдра шесть вершин \(A\), \(B\), \(C\), \(D\), \(M\), \(N\) и 12 рёбер: \(AM\), \(MC\), \(CN\), \(NA\), \(AB\), \(BC\), \(AD\), \(DC\), \(MB\), \(MD\), \(NB\), \(ND\). Степени вершин: \(A\) — 4, \(B\) — 4, \(C\) — 4, \(D\) — 4, \(M\) — 4, \(N\) — 4. Вершин нечётной степени нет вовсе, значит, граф октаэдра эйлеров, причём в нём есть эйлеров цикл \(MABCDANBMCNDM\): он проходит по рёбрам \(AM\), \(AB\), \(BC\), \(DC\), \(AD\), \(NA\), \(NB\), \(MB\), \(MC\), \(CN\), \(ND\), \(MD\) — по каждому из 12 рёбер ровно один раз — и возвращается в вершину \(M\).
Ответ: а) нет, граф куба не является эйлеровым; б) нет, граф тетраэдра не является эйлеровым; в) да, граф октаэдра является эйлеровым.
Рассмотрите рисунок 28 на с. 45. Является ли эйлеровым: а) граф куба; б) граф тетраэдра; в) граф октаэдра?
Связный конечный граф является эйлеровым тогда и только тогда, когда в нём не больше двух вершин нечётной степени. Все три графа связны, поэтому достаточно сосчитать в каждом вершины нечётной степени.
а) В графе куба восемь вершин \(A\), \(B\), \(C\), \(D\), \(K\), \(L\), \(M\), \(N\) и 12 рёбер: \(AD\), \(DN\), \(NK\), \(KA\), \(BC\), \(CM\), \(ML\), \(LB\), \(AB\), \(DC\), \(NM\), \(KL\).
Каждая вершина принадлежит ровно трём рёбрам. Степени вершин: \(A\) — 3, \(B\) — 3, \(C\) — 3, \(D\) — 3, \(K\) — 3, \(L\) — 3, \(M\) — 3, \(N\) — 3.
Вершин нечётной степени восемь, это больше двух. Значит, граф куба не является эйлеровым.
б) В графе тетраэдра четыре вершины \(A\), \(B\), \(C\), \(D\) и 6 рёбер: \(AB\), \(AC\), \(AD\), \(BC\), \(BD\), \(CD\).
Степени вершин: \(A\) — 3, \(B\) — 3, \(C\) — 3, \(D\) — 3.
Вершин нечётной степени четыре, это больше двух. Значит, граф тетраэдра не является эйлеровым.
в) В графе октаэдра шесть вершин \(A\), \(B\), \(C\), \(D\), \(M\), \(N\) и 12 рёбер: \(AM\), \(MC\), \(CN\), \(NA\), \(AB\), \(BC\), \(AD\), \(DC\), \(MB\), \(MD\), \(NB\), \(ND\).
Степени вершин: \(A\) — 4, \(B\) — 4, \(C\) — 4, \(D\) — 4, \(M\) — 4, \(N\) — 4.
Вершин нечётной степени нет вовсе, значит, граф октаэдра эйлеров, причём в нём есть эйлеров цикл. Вот он: \(MABCDANBMCNDM\). Этот путь проходит по рёбрам \(AM\), \(AB\), \(BC\), \(DC\), \(AD\), \(NA\), \(NB\), \(MB\), \(MC\), \(CN\), \(ND\), \(MD\) — по каждому из 12 рёбер ровно один раз — и возвращается в вершину \(M\).
Ответ: а) нет, граф куба не является эйлеровым; б) нет, граф тетраэдра не является эйлеровым; в) да, граф октаэдра является эйлеровым.
