Читать курсовая по математике: "Решения комбинаторных задач теории графов с помощью теоремы Пойа" Страница 2

(Назад) (Cкачать работу)

Путем называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги. Простой путь - путь, в котором ни одна дуга не встречается дважды. Элементарный путь - путь, в котором ни одна вершина не встречается дважды. Контур - путь, у которого конечная вер шина совпадает с начальной вершиной. Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы). [3]

Граф, для которогоиз следует,называется симметрическим. Если из следует, чтото соответствующий граф называется антисимметрическим.

Цепью называется множество ребер (в неориентированном графе), которые можно расположить так, что конец (в этом расположении) одного ребра является началом другого. Другое определение: цепь - последовательность смежных вершин. Замкнутая цепь называется циклом. По аналогии с простым и элементарным путем, можно определить соответственно простые и элементарные цепь и цикл. Любой элементарный цикл является простым, обратное утверждение в общем случае неверно. Элементарная цепь (цикл, путь, контур), проходящая через все вершины графа называется гамильтоновой цепью (соответственно - циклом, путем, контуром). Простая цепь (цикл, путь, контур), содержащая все ребра (дуги) графа называется эйлеровой цепью (соответственно - циклом, путем, контуром).

Если любые две вершины графа можно соединить цепью, то граф называется связным. Если граф не является связным, то его можно разбить на связные подграфы, называемые компонентами. Связностью графа называется минимальное число ребер, после удаления, которых граф становится несвязным. Для ориентированных графов, если любые две вершины графа можно соединить путем, то граф называется сильно связным. Известно , что: связность графа не может быть больше, чем [2m /n], где [x] - целая часть числа x; существуют графы с n вершинами и m ребрами, имеющие связность [2m /n]; в сильно связном графе через любые две вершины проходит контур. Связный граф, в котором существует эйлеров цикл, называется эйлеровым графом. В неориентированном графе степенью вершины i называется число di инцидентных ей ребер. Очевидно, dj < n - l , i ex . Граф, степени всех вершин которого равны n - 1, называется полным. Граф, все степени вершин которого равны, называется однородным. [2]

Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны (теорема Эйлера). Обозначим щ - число вершин, имеющих степень k, k = 0, 1, 2,... . Известно, что:Для ориентированных графов для каждой вершины можно ввести два числа - полу степень исхода(число выходящих из нее вершин) и полу степень захода

(число входящих в нее для эйлерова графа имеет место: d = di, вершин). В дальнейшем, если не оговорено особо, будем рассматривать графы без петель, то есть без дуг, у которых начальная и конечная вершины совпадают. Известно, что:эйлеров граф является объединением контуров, попарно не имеющих общих ребер.

Деревом называется связный граф без простых циклов, имеющий не менее двух вершин. Для дерева m = n-1, а число висячих вершин равно

.

Легко показать, что в дереве любые две вершины связаны единственной цепью.

Прадеревом называется

Похожие работы