ВУЗ:
Составители:
Рубрика:
Графы удобно представлять в виде рисунков, состоящих из то-
чек, изображающих вершины, и линий, соединяющих некоторые
из вершин, и изображающих ребра.
Определение.
Если ребро e инцидентно вершинами u и v, то та-
кие вершины называются граничными точками ребра e.
Определение
. Если u и v - граничные точки ребра e и u=v, то e
называется петлей (в этом случае u смежна сама с собой).
Определение.
Если вершины u и v инцидентны ребрам e
1
и e
2
,
то ребра e
1
и e
2
называются параллельными ребрами.
Определение.
Ребра e
1
и e
2
называются смежными, если они
имеют, по крайней мере, одну общую граничную точку.
Замечание.
Смежность является отношением между двумя по-
добными элементами (между вершинами или между ребрами), а
инцидентность есть отражение между разнородными элементами.
Определение
. Число ребер, инцидентных вершине v (петля учи-
тывается дважды), называется степенью вершины v и обозначается
δ
(v). Вершина v изолирована, если
δ
(v)=0.
Определение. Граф называется вырожденным (пустым) если
все его вершины являются изолированными.
Теорема.
В конечном графе число вершин нечетной степени
четно.
Доказательство
. Рассмотрим конечный граф G=(V,E). Пусть
⎢V ⎢ и ⎢E ⎢ число вершин и ребер соответственно. Учитывая, что
появление каждого нового ребра добавляет по единице к степеням
двух вершин (или в случае петли два к степени одной вершины),
имеем
() 2
vV
vE
δ
∈
=
∑
.
Если V
0
и V
1
- множества вершин, имеющих четные и нечетные
степени соответственно, то очевидно
∑
∈
0
Vv
v)(
δ
четно, как конечная
сумма четных чисел. Следовательно
∑
∑∑
∈∈∈
=−
10
VvVvVv
Vvv )()()(
δδδ
также обязательно четно. В сумме
1
()
vV
V
δ
∈
∑
слагаемыми являют-
ся нечетные степени вершин. Следовательно, количество
27
Страницы
- « первая
- ‹ предыдущая
- …
- 25
- 26
- 27
- 28
- 29
- …
- следующая ›
- последняя »
