Страница 59 номер 100, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Постройте граф, у которого число вершин на 3 меньше, чем число рёбер, и который имеет 8 циклов.
Число вершин на 3 меньше числа рёбер, значит, \(e - v = 3\), и у связного графа цикломатическое число равно \(e - v + 1 = 3 + 1 = 4\). Чтобы получить остовное дерево, нужно удалить 4 ребра, и при этом будут разомкнуты по крайней мере 4 цикла, поэтому меньше четырёх циклов в таком графе быть не может.
Возьмём полный граф на четырёх вершинах \(A\), \(B\), \(C\), \(D\) со всеми шестью рёбрами \(AB\), \(AC\), \(AD\), \(BC\), \(BD\), \(CD\) и добавим петлю при вершине \(A\). В нём \(v = 4\) вершины и \(e = 7\) рёбер, и действительно \(7 - 4 = 3\); граф связен, потому что любые две его вершины соединены ребром.
Цикл длины 1 — петля, и она в графе одна.
Циклов длины 2 нет: кратных рёбер в графе нет.
Цикл длины 3 — треугольник на каких-то трёх из четырёх вершин; троек вершин четыре, и каждая даёт ровно один треугольник, потому что все рёбра проведены: \(ABCA\), \(ABDA\), \(ACDA\), \(BCDB\) — всего 4 цикла.
Цикл длины 4 проходит через все четыре вершины, и каждая вершина в нём соединена ровно с двумя другими, поэтому такой цикл задаётся тем, какая вершина не соединена в нём с вершиной \(A\): это \(B\), \(C\) или \(D\). Циклы \(ACBDA\), \(ABCDA\), \(ABDCA\) — всего 3.
Циклов длины больше 4 нет: в цикле вершины не повторяются, а вершин в графе четыре.
Всего циклов \(1 + 4 + 3 = 8\).
Ответ: годится, например, граф с вершинами \(A\), \(B\), \(C\), \(D\), в котором проведены все шесть рёбер между ними и есть петля при вершине \(A\): в нём 4 вершины, 7 рёбер и ровно 8 циклов.
Постройте граф, у которого число вершин на 3 меньше, чем число рёбер, и который имеет 8 циклов.
Число вершин на 3 меньше числа рёбер, значит, \(e - v = 3\), и у связного графа с такими числами вершин и рёбер цикломатическое число равно \(e - v + 1 = 3 + 1 = 4\). Чтобы получить остовное дерево, нужно удалить 4 ребра, и при этом будут разомкнуты по крайней мере 4 цикла, поэтому меньше четырёх циклов в таком графе быть не может. Нужно подобрать граф, у которого их ровно восемь.
Возьмём полный граф на четырёх вершинах \(A\), \(B\), \(C\), \(D\): в нём проведены все шесть рёбер \(AB\), \(AC\), \(AD\), \(BC\), \(BD\), \(CD\). Добавим к нему петлю при вершине \(A\). В получившемся графе \(v = 4\) вершины и \(e = 7\) рёбер, и действительно \(7 - 4 = 3\); он связен, потому что любые две его вершины соединены ребром.
Сосчитаем циклы этого графа.
Цикл длины 1 — это петля, и она в графе одна.
Циклов длины 2 нет: кратных рёбер в графе нет.
Цикл длины 3 — это треугольник на каких-то трёх из четырёх вершин. Троек вершин четыре, и каждая даёт ровно один треугольник, потому что все рёбра между вершинами проведены: \(ABCA\), \(ABDA\), \(ACDA\), \(BCDB\). Всего 4 цикла.
Цикл длины 4 проходит через все четыре вершины, и в нём каждая вершина соединена ровно с двумя другими. Поэтому такой цикл однозначно задаётся тем, какая вершина не соединена в нём с вершиной \(A\): это \(B\), \(C\) или \(D\). Получаем три цикла: \(ACBDA\), \(ABCDA\) и \(ABDCA\).
Циклов длины больше 4 нет: в цикле вершины не повторяются, а вершин в графе всего четыре.
Всего циклов \(1 + 4 + 3 = 8\) — столько, сколько требуется.
Ответ: годится, например, граф с вершинами \(A\), \(B\), \(C\), \(D\), в котором проведены все шесть рёбер между ними и есть петля при вершине \(A\): в нём 4 вершины, 7 рёбер и ровно 8 циклов.
