Теория:
В путешествиях нам приходится тщательно выстраивать свой маршрут. Выбирать оптимальный путь из нескольких, которые предлагают нам онлайн-карты.
Мы помним, что графы применяют для изучения связей между различными объектами. Введём понятие пути в графе.
Путём в графе от вершины А до вершины B назовём такую последовательность рёбер графа, в которой каждые два соседних ребра имеют общую вершину.
Пример:
в графе на рис. \(1\) путь от точки A до точки B можно записать так:
AD — DB или AC — CD — DB.
Рис. \(1\). Граф
Длина пути — это количество рёбер в этом пути.
Пример:
в графе на рис. \(1\) длина пути AD — DB равна \(2\), а длина пути AC — CD — DB равна \(3\).
Путь в графе, у которого вершины не повторяются, называется цепью.
Цепь в графе можно задавать перечислением только вершин или только рёбер.
Например, A — C — D — B или AC — CD — DB.
Цикл в графе — это путь, у которого начало и конец — в одной вершине, а рёбра и промежуточные вершины не повторяются.
Обозначается цикл так: A — C — D — B — A или C — D — B — A — C.
Началом можно считать любую вершину графа.
Если существует путь, ведущий из одной вершины в другую, то эти вершины называются связанными.
Если в графе любые две вершины соединены путём, то такой граф называется связным.
Пример:
на рис. \(2\) вершины A и C, C и D, C и K, A и F, F и B — связанные, а сам граф является связным.
Рис. \(2\). Связный граф
Рис. \(3\). Несвязный граф
Граф, у которого каждая вершина соединена ребром с любой другой вершиной, называется полным.
Например, граф на рис. \(4\) является полным, так как каждая вершина соединена с другими.
Рис. \(4\). Полный граф
Найдём количество рёбер, выходящих из каждой вершины. Так как одна вершина должна быть соединена со всеми остальными, то рёбер будет \(3\).
Тогда по лемме о рукопожатиях можем найти количество всех рёбер.
\(=\) 6.
Сформулируем это правило в общем виде.
Чтобы найти количество рёбер в полном графе, у которого \(n\) вершин, нужно воспользоваться формулой:
.
Источники:
Рис. 1–4. Графы. © ЯКласс.