Алгоритм нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг — метод Дейкстры.
Записи с меткой ‘ДМ’
Алгоритм Дейкстры
Дата: 9th Июнь 2010. Автор: KAS. Рубрика: ГрафыМетки: алгоритмы, Дискретная математика, ДМ
0
Алгоритм Форда-Белмана
Дата: 8th Июнь 2010. Автор: KAS. Рубрика: АлгоритмыМетки: алгоритмы, Дискретная математика, ДМ
Алгоритм Форда-Белмана для поиска кратчайшего расстояния в графе. private void algFordaBelmana() { int s=Convert.ToInt32(textBox5.Text) — 1; //произвольная вершина графа, которая послужит началом пути int[] D=new int[n]; initGraph(); initMatrixWeight(); if (s < 0 || s >= n) return; for (int i = 0; i < n; i++) { D[i] = A[s, i]; } [...]
Циклом Гамильтона называется путь проходящий через каждую вершину графа только 1 раз. Псевдокод: procedure ГАМИЛЬТ(k) {генерация всех гамильтоновых циклов, являющихся расширением последовательности X[1], . . ., X[k – 1]: массив X — глобальный } begin for y принадлежит ЗАПИСЬ [X[k – 1]] do if (k = n +1) and (y = v0) then write(X[1], . [...]
Циклы Эйлера
Дата: 19th Апрель 2010. Автор: KAS. Рубрика: АлгоритмыМетки: алгоритмы, Дискретная математика, ДМ
Циклом Эйлера называется путь проходящий только 1 раз через каждое ребро графа. Для существования циклов Эйлера необходимо чтобы граф был связанный и все его вершины имели четную степень (кол-во ребер инцидентных вершине четно).
Алгоритм определения числа связности графа
Дата: 11th Апрель 2010. Автор: KAS. Рубрика: АлгоритмыМетки: алгоритмы, Дискретная математика, ДМ
Компонентом связности называют максимально связанный порожденный подграф. Числом связности графа – кол-во компонент связности.