Предыдущая страница реферата | 1  2  3  4  5 | Следующая страница реферата



Последоватедность вершин (x1, x2, x3, ...xN ) графа G называется путем если для любого i, принадл.[1..n] => {(x(i), x(i+1) )принадл.U и (x(i+1), x(i) )принадл.U}. Иными словами путь это цепь, рассматриваемая без учета ориентации вершин.

При этом n - длина пути, цепи соответственно.

Если x1=xN , то путь назывется циклом.

Если x1=xN в цепи, то цикл называется ориентированным.

Определение.

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

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

Определение.

Весом пути называется m(x1, x2, x3, ...xN) = m(x1, x2) + m(x2, x3) + ... + m(x(N-1), xN).

Типичные операции с графами:

 вставить вершину;

 удалить вершину;

 заменить вершину;

 добавить дугу;

 удалить дугу;

 найти в графе заданный подграф.

В терминах графов строка - линейный неориентированный граф.

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

3.3.Деревья

Определение.

Дерево - связный ациклический (без циклов) граф.

Подчеркнем что здесь в цикле ориентация дуг не учитывается.

Определение.

Одна вершина в дереве имеет степень захода 0. Эта вершина назывется корнем дерева.

Одна или несколько вершин в дереве имееют степень исхода 0. Эти вершины называются листьями.

Следствием условия ацикличности является то, что все вершины в графе, кроме корня, имеют сепень захода 1.

Рекомендуем скачать другие рефераты по теме: банк курсовых работ бесплатно, отчет по практике.

Предыдущая страница реферата | 1  2  3  4  5 | Следующая страница реферата