Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Бурков В.Н. Элементы теории графов
 
djvu / html
 

ных графов, если любые две вершины графа можно соединить
путем, то граф называется сильно связным. Известно [7], что:
связность графа не может быть больше, чем [2т / п], где [х] - целая
часть числа х; существуют графы с п вершинами и т ребрами,
имеющие связность [2т /п]; в сильно связном графе через любые
две вершины проходит контур.
Связный граф, в котором существует эйлеров цикл, называет-
ся эйлеровым графом.
В неориентированном графе степенью вершины i называется
число di инцидентных ей ребер. Очевидно, dt степени всех вершин которого равны п - 1, называется полным.
Граф, все степени вершин которого равны, называется однород-
ным.
Вершина, для которой не существует инцидентных ей ребер
(di = 0) называется изолированной. Вершина, для которой сущест-
вует только одно инцидентное ей ребро (dt = 1) называется вися-
чей.
Известно [7], что: /tdf = 2 т (данное выражение называется
кХ
«леммой о рукопожатиях» - поскольку в каждом рукопожатии
участвуют две руки, то при любом числе рукопожатий общее
число пожатых рук четно (при условии, что каждая рука учитыва-
ется столько раз, в скольких рукопожатиях она участвовала)); в
любом графе число вершин нечетной степени четно.
Связный граф является эйлеровым тогда и только тогда, когда
степени всех его вершин четны (теорема Эйлера). Обозначим и* -
число вершин, имеющих степень k, k = О, 1, 2,... . Известно [7, 15],
что: y\k nk = 2 т.
k:nt>0
Для ориентированных графов для каждой вершины можно
ввести два числа - полустепень исхода й?г+ (число выходящих из
нее вершин) и полустепень захода d^ (число входящих в нее
вершин). В дальнейшем, если не оговорено особо, будем рассмат-
ривать графы без петель, то есть без дуг, у которых начальная и
конечная вершины совпадают. Известно [7, 15], что:
Г = 2_,й?г+ = ти; для эйлерова графа имеет место: й?г+ = d^,

 

1 2 3 4 5 6 7 8 9 10 20


Математика