Степень (валентность) вершины. Путь в графе. Цепи и циклы

Степень (валентность) вершины. Путь в графе. Цепи и циклы. Статья к уроку №2 в 10 классе по Вероятности и статистике, плюс презентация с теорией и задачами.

Графы – это математические структуры, состоящие из множества вершин и рёбер, соединяющих эти вершины. Они широко используются для моделирования и решения различных задач в реальной жизни, таких как маршруты в транспортных сетях, связи в социальных сетях и многое другое. Сегодня мы познакомимся с такими важными понятиями, как степень вершины, путь, цепи и циклы.

Степень (валентность) вершины

Степень вершины – это количество рёбер, которые соединяются с этой вершиной. Степень вершины показывает, сколько других вершин связано с данной вершиной.

• Ненаправленный граф. В ненаправленном графе степень вершины – это просто количество рёбер, инцидентных этой вершине.

  Пример: В вершине A есть 3 ребра, соединяющие её с вершинами B, C и D. Степень вершины A равна 3.

• Направленный граф. В направленном графе различают входящую и исходящую степени вершины:

  • Входящая степень (in-degree): Количество рёбер, входящих в вершину.
  • Исходящая степень (out-degree): Количество рёбер, исходящих из вершины.

  Пример: В вершину A входят 2 ребра от вершин B и C, и из вершины A исходят 3 ребра к вершинам D, E и F. Входящая степень вершины A равна 2, исходящая степень равна 3.

Путь в графе

Путь – это последовательность вершин, в которой каждая пара последовательных вершин соединена ребром. Путь может быть направленным или ненаправленным, взвешенным или невзвешенным.

• Простой путь. Путь, в котором никакая вершина не повторяется.
• Замкнутый путь. Путь, который начинается и заканчивается в одной и той же вершине.

Пример: Рассмотрим граф с вершинами A, B, C, D. Путь из A в D может выглядеть так: A → B → C → D.

Цепи и циклы

Цепь – это последовательность рёбер, соединяющая определённые вершины, в которой каждая вершина появляется не более одного раза, за исключением возможно начальной и конечной вершины.

• Простая цепь. Цепь, в которой ни одна вершина не повторяется.

Цикл – это путь, который начинается и заканчивается в одной и той же вершине, и все рёбра и вершины (кроме начальной и конечной) уникальны.

• Простой цикл. Цикл, в котором никакая вершина (кроме начальной и конечной) не повторяется.

Пример: В графе с вершинами A, B, C, D, E может быть цикл: A → B → C → D → A.

Примеры из жизни

1. Транспортные маршруты.

   • Степень вершины. Город, в который входят и из которого выходят дороги, является вершиной графа. Степень вершины показывает, сколько дорог ведет к этому городу.
   • Путь. Маршрут автобуса или поезда от одного города до другого представляет собой путь в графе.
   • Цикл. Кольцевой маршрут автобуса, который возвращается в исходный пункт после посещения нескольких остановок, является циклом в графе.

2. Социальные сети.

   • Степень вершины. Пользователь социальной сети – это вершина, а его друзья – это рёбра. Степень вершины показывает количество друзей у пользователя.
   • Путь. Путь в графе может представлять цепочку друзей, через которых один пользователь может связаться с другим.
   • Цикл. Группа друзей, которые все связаны друг с другом, может быть представлена как цикл.

Заключение

Понимание таких понятий, как степень вершины, путь, цепи и циклы, помогает анализировать и решать разнообразные задачи в графах. Эти концепции являются важными инструментами в математике и её приложениях. Они позволяют моделировать сложные системы и процессы, улучшая наше понимание и умение работать с ними.

Ниже - разработанная презентация для урока №2 в 10 классе по Вероятности и статистике