Вопросы к пункту 1 «Связные графы» на странице 59, ГДЗ по алгебре за 10 класс к учебнику Бунимовича вероятность и статистика

Вопросы к пункту 1 «Связные графы».

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

Пример связного графа — схема линий метро: с любой станции можно доехать до любой другой, возможно, с пересадками. Если же граф распадается на части, между которыми нет ни одного ребра, он несвязный, а сами части называются компонентами связности.

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

Полный граф — это граф, в котором ребром соединена каждая пара вершин. Ни одной пары вершин без ребра между ними в нём нет, поэтому в полном графе с \(n\) вершинами степень каждой вершины равна \(n-1\), а сам граф связный.

Ответ: полный граф — это граф, в котором каждые две вершины соединены ребром.

Каждая из четырёх вершин соединена с тремя остальными, значит, степень каждой вершины равна 3, а сумма степеней всех вершин равна \(4 \cdot 3 = 12\). Сумма степеней вершин вдвое больше числа рёбер, поэтому рёбер \(12 : 2 = 6\).

Ответ: 6 рёбер.

Мостом называется ребро связного графа, после удаления которого граф становится несвязным — распадается на две компоненты связности.

Мостами являются в точности те рёбра, которые не входят ни в один цикл: если ребро, соединяющее вершины \(x\) и \(y\), лежит на цикле, то после его удаления от \(x\) до \(y\) можно пройти по оставшейся части этого цикла, и связность не нарушится.

Ответ: мост — это ребро связного графа, при удалении которого граф распадается на две компоненты; мостами служат ровно те рёбра, которые не лежат ни на одном цикле.