Вопросы после параграфа §9 на странице 44, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни

Деревом называется связный граф без циклов.

Связность значит, что любые две вершины графа соединены путём. Отсутствие циклов значит, что в графе нет ни петли (это цикл длины 1), ни пары кратных рёбер (это цикл длины 2), ни цикла большей длины.

Простейшее дерево состоит из одной-единственной вершины и не содержит рёбер. Любая цепь — тоже дерево: она связна, а вершины в ней не повторяются, поэтому замкнуться ей не на чем.

Ответ: дерево — это связный граф, в котором нет циклов.

Длина конечного пути — это количество рёбер в нём. Каждое ребро учитывается столько раз, сколько раз оно входит в путь.

Например, пусть вершины \(A\), \(B\), \(C\) попарно соединены рёбрами. Тогда длина пути \(ABCA\) равна 3: в него входят рёбра \(AB\), \(BC\), \(CA\). Длина пути \(ABAB\) тоже равна 3, хотя разных рёбер в нём всего одно: ребро \(AB\) пройдено три раза, и все три раза оно засчитано.

Ответ: длина конечного пути — это число рёбер в нём, причём каждое ребро считается столько раз, сколько раз оно в путь входит.

а) Истинно. Цепь по определению — это путь без повторяющихся вершин, то есть цепь прежде всего является путём.

б) Ложно. Контрпример: пусть вершины \(A\) и \(B\) соединены ребром. Последовательность \(ABA\) — путь, потому что каждые две соседние вершины в ней соединены ребром. Но вершина \(A\) в этой последовательности повторяется, значит, цепью она не является.

в) Истинно. Цикл длины \(n\) образован рёбрами \(V_1V_2\), \(V_2V_3\), ..., \(V_{n-1}V_n\), \(V_nV_1\) и записывается последовательностью вершин \(V_1V_2\ldots V_nV_1\). В этой последовательности каждые две соседние вершины соединены ребром, а это и есть определение пути.

г) Ложно. Дерево — связный граф без циклов, поэтому цикла в дереве нет ни одного.

Ответ: истинны утверждения а) «каждая цепь — путь» и в) «каждый цикл — путь»; ложны утверждения б) «каждый путь — цепь» и г) «в каждом дереве есть цикл».

Возьмём граф треугольника: вершины \(A\), \(B\), \(C\) и рёбра \(AB\), \(BC\), \(CA\). Любые две его вершины соединены ребром, значит, этот граф связен.

Удалим из него два ребра — \(BC\) и \(CA\), — оставив все три вершины. Получится подграф с единственным ребром \(AB\). Вершина \(C\) в нём изолирована: к ней не примыкает ни одно ребро, и никаким путём с вершинами \(A\) и \(B\) она не связана. Значит, этот подграф несвязен, у него две компоненты связности: \(\{A,\ B\}\) и \(\{C\}\).

Ответ: треугольник с вершинами \(A\), \(B\), \(C\) и рёбрами \(AB\), \(BC\), \(CA\) связен, а его подграф на тех же трёх вершинах с единственным ребром \(AB\) несвязен — вершина \(C\) в этом подграфе изолирована.

Возьмём граф с вершинами \(A\), \(B\), \(C\), \(D\), \(E\) и рёбрами \(AB\), \(BC\), \(CA\), \(DE\). Вершину \(A\) с вершиной \(D\) не соединяет никакой путь: из \(A\) по рёбрам можно попасть только в \(B\) и \(C\). Значит, этот граф не связен, у него две компоненты связности — треугольник \(ABC\) и ребро \(DE\).

Удалим вершины \(D\) и \(E\) вместе с примыкающим к ним ребром \(DE\). Останется подграф — треугольник с вершинами \(A\), \(B\), \(C\) и рёбрами \(AB\), \(BC\), \(CA\). В нём любые две вершины соединены ребром, значит, подграф связен.

Ответ: граф с вершинами \(A\), \(B\), \(C\), \(D\), \(E\) и рёбрами \(AB\), \(BC\), \(CA\), \(DE\) не связен, а его подграф — треугольник с вершинами \(A\), \(B\), \(C\) — связен.

Цикл длины 1 состоит из одной вершины и одного ребра, соединяющего эту вершину с ней же самой. Ребро, которое соединяет вершину графа с этой же вершиной, называется петлёй.

Ответ: цикл длины 1 называется петлёй.

Полным графом называется граф без петель и кратных рёбер, в котором две любые вершины соединены ребром.

Полный граф с \(n\) вершинами обозначают \(K_n\). Каждое его ребро задаётся парой различных вершин, и разные рёбра задают разные пары, поэтому рёбер в нём ровно столько, сколько пар можно выбрать из \(n\) вершин: \(C_n^2 = \frac{n(n-1)}{2}\). Например, \(K_3\) — граф треугольника, у него 3 ребра; \(K_4\) — граф тетраэдра, у него 6 рёбер.

Ответ: полный граф — это граф без петель и кратных рёбер, в котором две любые вершины соединены ребром; полный граф \(K_n\) с \(n\) вершинами имеет \(\frac{n(n-1)}{2}\) рёбер.