Вычисление пределов
Криволинейный интеграл
Карта сайта

Дискретная математика Деревья и циклы

 

 Определение. Граф G называется деревом, если он является связным и не имеет циклов. Граф G, все компоненты связности которого являются деревьями, называется лесом.

 У графа, который является деревом, число ребер на единицу меньше числа вершин. Дерево не содержит циклов, любые две его вершины можно соеденить единственной простой цепью.

 

 

 

 

 

 

 Если у дерева G есть, по крайней мере, одно ребро, то у него обязательно найдется висячая вершина, т.к. в противном случае в графе будет цикл.

 Приложения криволинейных интегралов 2-ого рода. Рассмотрим криволинейный интеграл 2-ого рода J = P(x,y,z)dx + Q(x,y,z)dy + R(x,y,z)dz Математика лекции и задачи

 Для графов, которые сами по себе не являются деревьями, вводится понятие остовного дерева.

 

 Определение. Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

 Пусть G – связный граф. Тогда остовное дерево графа G (если оно существует) должно содержать n(G)-1 ребер.

 Таким образом, любое остовное дерево графа G есть результат удаления из графа G ровно m(G) - (n(G) - 1) = m(G) – n(G) + 1 ребер.

 Число v(G) = m(G) – n(G) + 1 называется цикломатическим числом связного графа G.

 Одной из самых распространенных задач является задача построения остовного дерева минимальной длины графа. Для решения этой задачи применяется следующий алгоритм.

 1) Выберем в графе G ребро минимальной длины. Вместе с инциндентными ему вершинами оно образует подграф G2.

 2) Строим граф G3, добавляя к графу G2 новое ребро минимальной длины, выбранное среди ребер графа G, каждое из которых инциндентно какой либо вершине графа G2, и одновременно инциндентно какой – либо вершине графа G, не содержащейся в графе G2.

 3) Строим графы G4, G5, …, Gn, повторяя действия пункта 2 до тех пор, пока не переберем все вершины графа G.

  [an error occurred while processing this directive]

 Пример. Определить минимальное остовное дерево нагруженного графа.

 

 Граф называется нагруженным, если на множестве его дуг задана некоторая функция, которая называется весовой функцией, и определяет длину дуги.

 В нашем примере – весовая функция определяет длины дуг числами 1, 2, 3, 4, 5.

 v2 2 v3

 


 

 На четвертом шаге алгоритма получили дерево G5, которое соединяет все вершины исходного графа. Таким образом, дерево G5 , будет минимальным остовным деревом графа

 


На главную страницу сайта