64 Сколько компонент связности в графе, изображённом: а) на рисунке 27, а; б) на рисунке 27, б?

Решение:

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

• а) на рисунке 27, а: Граф состоит из вершин A, B, C, D, E. Все вершины соединены между собой так, что можно добраться из любой вершины в любую другую. Следовательно, это одна компонента связности.
• б) на рисунке 27, б: Граф состоит из вершин A, B, C, D. Все вершины соединены между собой так, что можно добраться из любой вершины в любую другую. Следовательно, это одна компонента связности.

Ответ: а) 1; б) 1.