в ориентированном графе сумма исходящих степеней всех вершин равна 34. чему равна сумма входящих степеней всех вершин? количество ребер графа?
Давайте разберем задачу по шагам и подробно объясним каждое понятие и выводы.
Условие:
В ориентированном графе сумма исходящих степеней всех вершин равна 34.
Нужно найти:
- Сумму входящих степеней всех вершин.
- Количество рёбер графа.
Что такое степень вершины в ориентированном графе?
- Исходящая степень (deg_out(v)) — количество рёбер, исходящих из вершины v.
- Входящая степень (deg_in(v)) — количество рёбер, входящих в вершину v.
Свойство ориентированного графа:
В ориентированном графе сумма всех входящих степеней равна сумме всех исходящих степеней.
Это логично, потому что каждое ребро считается один раз слева (при входе) и один раз справа (при исходе), но при этом каждое ребро соединяет две вершины, один из которых «отдает» ребро (исходящая степень), а другой — «принимает» его (входящая степень).
Следствия из этого:
Пусть \( V \) — множество вершин, \( E \) — множество рёбер.
Тогда:
\[ \sum_{v \in V} \deg_{out}(v) = |E| \] потому что сумма всех исходящих степеней равна количеству рёбер (каждое ребро ведет из одной вершины в другую, и считается в исходящей степени исходной вершины).Аналогично:
\[ \sum_{v \in V} \deg_{in}(v) = |E| \]Также, сумма входящих степеней равна сумме исходящих степеней:
\[ \sum_{v \in V} \deg_{in}(v) = \sum_{v \in V} \deg_{out}(v) \]
Ответ на задачу:
Дано:
\[
\sum_{v \in V} \deg_{out}(v) = 34
\]
Следовательно,
\[
\boxed{
\sum_{v \in V} \deg_{in}(v) = 34
}
\]
и количество рёбер:
\[
|E| = \sum_{v \in V} \deg_{out}(v) = 34
\]
Итог:
- Сумма входящих степеней всех вершин равна 34.
- Количество рёбер графа равно 34.
Если у вас есть ещё вопросы или нужно более подробно — спрашивайте!
