Учебник «Вероятность и статистика. 7–9 классы», часть 1, с. 88, §20
№137. Изобразите два графа с шестью вершинами степени 2: один связный, а другой — нет.
Дано:
граф с шестью вершинами, у каждой вершины степень 2
Найти:
два таких графа: один связный, другой несвязный
Степень вершины — число рёбер, выходящих из неё (п. 19). Нужно нарисовать два графа, у каждого из которых шесть вершин и из каждой вершины выходит ровно два ребра. Граф называют связным, если из любой его вершины можно добраться по рёбрам до любой другой (п. 20).
а) Связный граф. Расставим шесть вершин по кругу и соединим каждую с двумя соседними: А—Б, Б—В, В—Г, Г—Д, Д—Е, Е—А. Получился цикл из шести вершин (шестиугольник). У каждой вершины ровно два ребра, и по рёбрам можно дойти от любой вершины до любой другой, например, от А до Г: А → Б → В → Г. Значит, граф связный.
б) Несвязный граф. Возьмём два отдельных треугольника: А—Б—В и Г—Д—Е. Вершин по-прежнему шесть, и у каждой вершины ровно два ребра (у вершины А — рёбра АБ и АВ, у Г — рёбра ГД и ГЕ и т. д.). Но между треугольниками рёбер нет, поэтому от вершины А до вершины Г добраться нельзя. Граф состоит из двух частей — он несвязный.
Других вариантов почти нет: если у каждой вершины ровно два ребра (и нет петель и кратных рёбер), граф распадается на циклы, а в каждом цикле не меньше трёх вершин. Шесть вершин можно разбить на циклы только двумя способами: один цикл из шести вершин (связный граф) или два цикла по три вершины (несвязный граф).
Ответ: Связный граф — шестиугольник (цикл из шести вершин). Несвязный граф — два отдельных треугольника.
