Страница 45 номер 64, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Сколько компонент связности в графе, изображённом: а) на рисунке 27, \(а\); б) на рисунке 27, \(б\)?
а) Пять вершин \(A\), \(B\), \(C\), \(D\), \(E\) и шесть рёбер: \(AD\), \(AE\), \(EC\), \(BE\), \(ED\), \(BC\). Вершина \(E\) соединена рёбрами \(AE\), \(BE\), \(EC\), \(ED\) с каждой из остальных вершин, поэтому любые две вершины соединены путём через \(E\): например, \(A\) и \(C\) — путём \(AEC\), а \(D\) и \(B\) — путём \(DEB\). Граф связен, компонента связности у него одна.
б) Четыре вершины \(A\), \(B\), \(C\), \(D\) и пять рёбер: \(AD\), \(AC\), \(BD\), \(BC\), \(DC\). Вершина \(D\) соединена рёбрами \(AD\), \(BD\), \(DC\) с каждой из остальных вершин, поэтому любые две вершины соединены путём через \(D\): например, \(A\) и \(B\) — путём \(ADB\). Точка пересечения отрезков \(AC\) и \(BD\) вершиной графа не является и на связность не влияет. Граф связен, компонента связности у него одна.
Ответ: а) одна компонента связности; б) одна компонента связности.
Сколько компонент связности в графе, изображённом: а) на рисунке 27, \(а\); б) на рисунке 27, \(б\)?
Граф называется связным, если две любые его вершины соединены путём. Связный граф состоит из одной компоненты связности. Чтобы сосчитать компоненты, достаточно проверить, откуда куда можно пройти по рёбрам.
а) В графе пять вершин — \(A\), \(B\), \(C\), \(D\), \(E\) — и шесть рёбер: \(AD\), \(AE\), \(EC\), \(BE\), \(ED\), \(BC\).
Вершина \(E\) соединена ребром с каждой из остальных вершин: ребро \(AE\) ведёт в \(A\), ребро \(BE\) — в \(B\), ребро \(EC\) — в \(C\), ребро \(ED\) — в \(D\). Поэтому любые две вершины графа соединены путём: из одной идём в \(E\), из \(E\) — в другую. Например, вершины \(A\) и \(C\) соединяет путь \(AEC\), а вершины \(D\) и \(B\) — путь \(DEB\).
Значит, граф связен, и компонента связности у него одна.
б) В графе четыре вершины — \(A\), \(B\), \(C\), \(D\) — и пять рёбер: \(AD\), \(AC\), \(BD\), \(BC\), \(DC\).
Вершина \(D\) соединена ребром с каждой из остальных вершин: ребро \(AD\) ведёт в \(A\), ребро \(BD\) — в \(B\), ребро \(DC\) — в \(C\). Значит, любые две вершины соединены путём через \(D\): например, \(A\) и \(B\) соединяет путь \(ADB\).
Отрезки \(AC\) и \(BD\) на рисунке пересекаются, но точка их пересечения вершиной графа не является; на связность это никак не влияет — все четыре вершины и без того связаны друг с другом.
Значит, граф связен, и компонента связности у него одна.
Ответ: а) одна компонента связности; б) одна компонента связности.
