Страница 45 номер 63, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Перечислите все циклы в графе, изображённом на рисунке 27.
Цикл записывают цепочкой вершин, в конце которой повторена первая вершина; тот же цикл с другой начальной вершины или в обратную сторону остаётся тем же самым циклом. В цикле длины 3 и больше каждая вершина участвует ровно в двух его рёбрах, поэтому цикл через вершину, у которой всего два ребра, обязан содержать оба этих ребра.
а) Рёбра графа: \(AD\), \(AE\), \(EC\), \(BE\), \(ED\), \(BC\). Петель и кратных рёбер нет, поэтому циклов длины 1 и 2 в графе нет.
Вершина \(A\) участвует ровно в двух рёбрах — \(AD\) и \(AE\), а вершина \(D\) — в рёбрах \(DA\) и \(DE\), поэтому из \(D\) цикл идёт по ребру \(DE\) и замыкается в \(E\): единственный цикл с вершиной \(A\) — это \(AEDA\) длины 3.
Вершина \(B\) участвует ровно в двух рёбрах — \(BE\) и \(BC\), а вершина \(C\) — в рёбрах \(CB\) и \(CE\), поэтому цикл с вершиной \(B\) — это \(BCEB\) длины 3.
Цикл без вершин \(A\) и \(B\) состоял бы из вершин \(C\), \(D\), \(E\), но ребра \(CD\) в графе нет. Циклов ровно два: \(AEDA\) и \(BCEB\).
б) Рёбра графа: \(AD\), \(AC\), \(BD\), \(BC\), \(DC\); петель и кратных рёбер тоже нет. Точка пересечения отрезков \(AC\) и \(BD\) вершиной графа не является, поэтому свернуть в ней с одного ребра на другое нельзя и цикла через неё не существует.
Вершина \(A\) участвует ровно в двух рёбрах — \(AD\) и \(AC\). Из вершины \(C\) цикл идёт либо в \(D\) по ребру \(CD\) и замыкается — получается \(ACDA\) длины 3, — либо в \(B\); но вершина \(B\) участвует только в рёбрах \(BC\) и \(BD\), поэтому из \(B\) цикл идёт в \(D\) и замыкается — получается \(ACBDA\) длины 4.
Цикл без вершины \(A\) состоит из вершин \(B\), \(C\), \(D\) с рёбрами \(BC\), \(CD\), \(DB\) — это цикл \(BCDB\) длины 3.
Циклов ровно три: \(ACDA\), \(ACBDA\) и \(BCDB\).
Ответ: а) два цикла — \(AEDA\) и \(BCEB\); б) три цикла — \(ACDA\), \(ACBDA\) и \(BCDB\).
Перечислите все циклы в графе, изображённом на рисунке 27.
Циклом длины \(n\) называется граф на вершинах \(V_1\), \(V_2\), ..., \(V_n\) с рёбрами \(V_1V_2\), \(V_2V_3\), ..., \(V_{n-1}V_n\), \(V_nV_1\); записывают его цепочкой вершин, в конце которой повторена первая вершина. Цикл — подграф данного графа, поэтому один и тот же цикл, записанный с другой начальной вершины или в обратную сторону, остаётся тем же самым циклом, и второй раз его выписывать не надо.
Цикл длины 1 — это петля, цикл длины 2 — пара кратных рёбер, а в цикле длины 3 и больше каждая вершина участвует ровно в двух его рёбрах. Значит, в графе без петель и кратных рёбер перебор удобно вести так: если вершина участвует всего в двух рёбрах, то цикл, содержащий эту вершину, обязан содержать оба этих ребра. На рисунке два графа, разберём каждый.
а) Рёбра графа: \(AD\), \(AE\), \(EC\), \(BE\), \(ED\), \(BC\). Петель и кратных рёбер нет, поэтому циклов длины 1 и 2 в графе нет — ищем циклы длины 3 и больше.
Вершина \(A\) участвует ровно в двух рёбрах: \(AD\) и \(AE\). Значит, цикл, содержащий \(A\), содержит оба этих ребра, а с ними вершины \(D\) и \(E\). Вершина \(D\) участвует в рёбрах \(DA\) и \(DE\), поэтому из \(D\) цикл идёт по ребру \(DE\) и замыкается в \(E\). Получается единственный цикл с вершиной \(A\) — это \(AEDA\) длины 3.
Точно так же вершина \(B\) участвует ровно в двух рёбрах — \(BE\) и \(BC\), а вершина \(C\) — в рёбрах \(CB\) и \(CE\). Значит, цикл, содержащий \(B\), — это \(BCEB\) длины 3.
Цикл без вершин \(A\) и \(B\) состоял бы из вершин \(C\), \(D\), \(E\), но ребра \(CD\) в графе нет, поэтому такого цикла не существует. Значит, циклов ровно два: \(AEDA\) и \(BCEB\).
б) Рёбра графа: \(AD\), \(AC\), \(BD\), \(BC\), \(DC\); петель и кратных рёбер здесь тоже нет, так что все циклы имеют длину 3 и больше. Отрезки \(AC\) и \(BD\) на рисунке пересекаются, но точка их пересечения вершиной графа не является — кружка там нет, — поэтому свернуть в этой точке с одного ребра на другое нельзя, и цикла через неё не существует.
Вершина \(A\) участвует ровно в двух рёбрах: \(AD\) и \(AC\). Значит, цикл, содержащий \(A\), содержит оба этих ребра. Из вершины \(C\) он идёт дальше либо в \(D\) по ребру \(CD\) — тогда цикл замыкается и получается \(ACDA\) длины 3, — либо в \(B\) по ребру \(CB\); но вершина \(B\) участвует только в рёбрах \(BC\) и \(BD\), поэтому из \(B\) цикл идёт в \(D\) и замыкается: получается \(ACBDA\) длины 4.
Цикл без вершины \(A\) состоит из вершин \(B\), \(C\), \(D\), попарно соединённых рёбрами \(BC\), \(CD\), \(DB\), — это цикл \(BCDB\) длины 3.
Значит, циклов ровно три: \(ACDA\), \(ACBDA\) и \(BCDB\).
Ответ: а) два цикла — \(AEDA\) и \(BCEB\); б) три цикла — \(ACDA\), \(ACBDA\) и \(BCDB\).
