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


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

Завершив краткое описание прикладных областей, вернемся к
введению основных понятий теории графов.
Подграфом называется часть графа, образованная подмноже-
ством вершин вместе со всеми ребрами (дугами), соединяющими
вершины из этого множества. Если из графа удалить часть ребер
(дуг), то получим частичный граф.
Две вершины называются смежными, если они соединены
ребром (дугой). Смежные вершины называются граничными вер-
шинами соответствующего ребра (дуги), а это ребро (дуга) - инци-
дентным соответствующим вершинам.
Путем называется последовательность дуг (в ориентирован-
ном графе), такая, что конец одной дуги является началом другой
дуги. Простой путь - путь, в котором ни одна дуга не встречается
дважды. Элементарный путь - путь, в котором ни одна вершина
не встречается дважды. Контур - путь, у которого конечная вер-
шина совпадает с начальной вершиной. Длиной пути (контура)
называется число дуг пути (или сумма длин его дуг, если послед-
ние заданы).
Граф, для которого из (i,j) ? V следует (/, г) е V называется
симметрическим. Если из (г, у) е V следует, что (/, г) "е" V, то соот-
ветствующий граф называется антисимметрическим.
Цепью называется множество ребер (в неориентированном
графе), которые можно расположить так, что конец (в этом распо-
ложении) одного ребра является началом другого. Другое опреде-
ление: цепь - последовательность смежных вершин. Замкнутая
цепь называется циклом. По аналогии с простым и элементарным
путем, можно определить соответственно простые и элементар-
ные цепь и цикл. Любой элементарный цикл является простым,
обратное утверждение в общем случае неверно. Элементарная цепь
(цикл, путь, контур), проходящая через все вершины графа называ-
ется гамилътоновой цепью (соответственно - циклом, путем, кон-
туром). Простая цепь (цикл, путь, контур), содержащая все ребра
(дуги) графа называется эйлеровой цепью (соответственно - цик-
лом, путем, контуром).
Если любые две вершины графа можно соединить цепью, то
граф называется связным. Если граф не является связным, то его
можно разбить на связные подграфы, называемые компонентами.
Связностью графа называется минимальное число ребер, после
удаления которых граф становится несвязным. Для ориентирован-
4

 

1 2 3 4 5 6 7 8 9 10 20


Математика