Рис. 79 a) б) B) 121. Определите, существует ли описанный ниже граф. Если да, то постройте его: а) граф из семи вершин, в котором все вершины имеют степень 2; б) граф из восьми вершин, в котором все вершины имеют степень 2; в) граф из восьми вершин, в котором все вершины имеют степень 1; г) граф из семи вершин, в котором все вершины имеют степень 1; д) граф из семи вершин, в котором все вершины имеют степень 3; е) граф из восьми вершин, в котором все вершины имеют степень 3. 122. Нарисуйте полные графы: а) из трёх вершин; б) из четырёх вершин; в) из пяти вершин; г) из п вершин. 123. Найдите число компонент связности для каждого из трёх графов, изображённых на рисун- ке 80.

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

Рассмотрим каждый из графов на рисунке 80:

1. Граф a)

   Здесь можно увидеть, что граф состоит из одной основной части, где все вершины соединены между собой, и нескольких изолированных вершин, не связанных с основной частью. Визуально граф можно разделить на две компоненты связности: основную часть и отдельные изолированные вершины. Таким образом, граф имеет 2 компоненты связности.

2. Граф б)

   Этот граф выглядит как один большой связанный кусок. Все вершины соединены между собой, образуя единую структуру. Нет изолированных вершин или отдельных частей, не связанных с основной структурой. Следовательно, данный граф имеет 1 компоненту связности.

3. Граф в)

   Этот граф состоит из нескольких отдельных, не связанных между собой вершин. Каждая вершина представляет собой отдельную компоненту связности, так как между ними нет путей. В данном графе 11 компонент связности.