Неориентированный граф: ребра KL),(K,M),(KN),(,N),(M,N). Найдите степени вершин и их сумму
Краткий ответ:
Если четвёртое ребро — это \((L,N)\), то
\[
\deg K=3,\quad \deg L=2,\quad \deg M=2,\quad \deg N=3,
\]
а сумма степеней вершин:
\[
3+2+2+3=10.
\]
Как считать: степень вершины — это число рёбер, которые из неё выходят.
Список рёбер: \[ KL,\ KM,\ KN,\ LN,\ MN. \]
| Вершина | С какими вершинами соединена | Степень |
|---|---|---|
| \(K\) | \(L,M,N\) | \(3\) |
| \(L\) | \(K,N\) | \(2\) |
| \(M\) | \(K,N\) | \(2\) |
| \(N\) | \(K,L,M\) | \(3\) |
Проверка: у графа \(5\) рёбер. Каждое ребро даёт по единице в степень двух своих концов, поэтому сумма всех степеней должна быть \[ 2\cdot 5=10. \] Полученная сумма \(10\) совпадает, значит всё верно.
Обсуждение
6 сообщенийА как считать степени, если в графе есть петля? Неориентированный граф: ребра (K,L),(K,M),(KN),(L,N),(M,N). Найдите степени вершин и их сумму
Петля — это ребро, у которого оба конца совпадают, например \((K,K)\).
Как считать степень с петлёй: петля даёт +2 к степени вершины, потому что она «входит» в эту вершину двумя концами. Поэтому формула \[ \sum \deg v=2\cdot |E| \] сохраняется: каждое ребро, включая петлю, считается один раз в числе рёбер.
Пример: если к графу добавить петлю \((K,K)\), то \[ \deg K=3+2=5, \] остальные степени не изменятся, а сумма станет \(12\).
В вашем графе петель нет. Рёбра: \[ (K,L),\ (K,M),\ (K,N),\ (L,N),\ (M,N). \]
| Вершина | Степень |
|---|---|
| \(K\) | \(3\) |
| \(L\) | \(2\) |
| \(M\) | \(2\) |
| \(N\) | \(3\) |
Сумма: \[ 3+2+2+3=10. \]
Проверка: рёбер \(5\), значит сумма степеней должна быть \(2\cdot5=10\). Всё сходится.
Неориентированный граф: ребра KL),(K,M),(KN),(L,N),(M,N). Найдите степени вершин и их сумму.
Ответ: \(\deg K=3,\ \deg L=2,\ \deg M=2,\ \deg N=3\), сумма степеней — \(10\).
Рёбра: \((K,L),\ (K,M),\ (K,N),\ (L,N),\ (M,N)\), петель нет — значит степень вершины равна числу рёбер, в которые она входит.
| Вершина | Соседи | Степень |
|---|---|---|
| \(K\) | \(L,\ M,\ N\) | \(3\) |
| \(L\) | \(K,\ N\) | \(2\) |
| \(M\) | \(K,\ N\) | \(2\) |
| \(N\) | \(K,\ L,\ M\) | \(3\) |
\[ \deg K+\deg L+\deg M+\deg N=3+2+2+3=10. \]
Проверка: рёбер \(5\), и каждое даёт по единице в степень двух своих концов, поэтому сумма должна быть \[ 2\cdot 5=10. \] Совпало — значит степени найдены верно.
Орграф: дугиА-С,А-D, В-А, С-В D-В, D->С. Найдите полустепени deg-, deg+ вершин и проверьте равенство сумм
Считаю, что запись \(X-Y\) означает дугу \(X\to Y\). Тогда дуги: \[ A\to C,\quad A\to D,\quad B\to A,\quad C\to B,\quad D\to B,\quad D\to C. \]
Обозначения: \(\deg^+v\) — полустепень выхода, \(\deg^-v\) — полустепень входа.
| Вершина | Исходящие дуги | \(\deg^+\) | Входящие дуги | \(\deg^-\) |
|---|---|---|---|---|
| \(A\) | \(A\to C,\ A\to D\) | \(2\) | \(B\to A\) | \(1\) |
| \(B\) | \(B\to A\) | \(1\) | \(C\to B,\ D\to B\) | \(2\) |
| \(C\) | \(C\to B\) | \(1\) | \(A\to C,\ D\to C\) | \(2\) |
| \(D\) | \(D\to B,\ D\to C\) | \(2\) | \(A\to D\) | \(1\) |
Суммы: \[ \sum \deg^+ = 2+1+1+2=6, \] \[ \sum \deg^- = 1+2+2+1=6. \]
Равенство выполняется: \[ \sum \deg^+=\sum \deg^-=6, \] что равно числу дуг орграфа. Это и есть проверка: каждая дуга даёт единицу в полустепень выхода начальной вершины и единицу в полустепень входа конечной.
