Найти все деревья графа

Найти все деревья графа

Название темы должно быть информативным !
Прежде чем задать вопрос, воспользуйтесь Поиском . и проверьте в FAQ (ЧАВО) Паскаля
Чтобы получить вразумительный ответ, подробно опишите проблему: что надо сделать, что не получается и номер ошибки (если есть), которую выводит компилятор. Для вставки кода ваших программ используйте, пожалуйста, кнопку СODE=pas или выпадающий список СODE для других языков (подсветка синтаксиса). [!] Как правильно задавать вопросы | Руководство по языку B.Pascal 7 & Objects/LR | Borland Pascal. Руководство пользователя

Понимаю, что немного нагло, но не могу сделать задачку, а сроки уже поджимают. Наверняка кто-нибудь делал, хоть примерно подскажите кто знает.

Задачка:
Найти все остовные деревья графа, используя алгоритм Краскала и схему перебора с возвратом. Граф задан массивом ребер.

Помогите решить задачу, если не трудно, сам я не могу, а спросить не у кого:
Найти сумму ряда с точностью ε=10 в степени (-3), общий член которого
Аn=(n!)/(2n)!

Dn$, алгоритм Краскала (как и алгоритм Прима) находит минимальный остов графа, а не все. Так что эта задача в принципе не может иметь решения.

Eiden, а может переименовать тему и назвать ее «Место помощи утопающим»?

Leonid, алгоритм элементарный: пихаешь свое выражение в цикл. Условие выхода из цикла:

Источник

2.6. Операции над графами

2.7. Задача о кратчайшем пути связного неориентированного графа

Дан неориентированный граф G ( X , Г ), каждому ребру v = ( x i , x j ) которого приписано некоторое число l ( v ) ³ 0 , называемое длиной ребра. При этом любая

цепь μ будет характеризоваться длиной l ( m ) = å l ( v ) .	Требуется среди всех
v Î V
возможных путей между произвольными вершинами x i	и x j найти такой, что-

бы его полная длина была наименьшей. Рассмотрим алгоритм определения кратчайшего пути, использующий индексацию вершин графа. 1. Каждая вершина х к рассматриваемого графа должна быть помечена индексом λ к . Конечной вершине х j первоначально присваивается индекс λ j =0. 2. На следующем шаге двигаемся от конечной вершины по инцидентным ребрам в сторону начальной вершины х i . Вторым вершинам этих ребер присваивается индекс λ j , численно равный длине ребра l ( х j х i ) от конечной точки до данной. 3. От каждой оцифрованной вершины двигаемся по инцидентным ребрам в сторону начальной вершины и вторым их концам присваиваем индексы, численно равные сумме величины индекса предыдущей вершины и длины данного ребра графа: l n = l 1 + l ( x 1 , x n ) . К каждой вершине можно подойти нескольки- ми путями, поэтому осуществляется процесс замены индексов, т. е. для каждой вершины следует найти такой индекс, который был бы наименьшим. Процедура продолжается, пока не будет оцифрована начальная вершина х i . Индекс λ i начальной вершины будет равен длине кратчайшего пути. 4. Кратчайший путь будет проходить через вершины х к , х n , начиная с х i , разность индексов которых λ k — λ n численно равна длине ребра. 37

В качестве примера рас-				B	0
смотрим граф,		приведенный		9	9
на рис. 2.22.	3
		3
Ребрам			графа приписаны			4
	8
		числа, которые					в	условных	13	5	4	7
единицах				соответствуют их									4
	длине. Нужно найти кратчай-						3	6		7
ший путь между вершинами А				7	2	7
и В . Индексы вершин			записа-	7	1	5
ны в кружочках. Кратчайший					A	9
				10
путь выделен на рисунке жир-

ной линией. Рис. 2.22

2.8. Деревья. Символ дерева

Деревом называется конечный связный неориентированный граф, не имеющий циклов. Деревья обладают следующими свойствами: 1) любые две вершины дерева связаны простой цепью; 2) дерево с n вершинами имеет n- 1 ребер; 3) число N различных деревьев, которые можно построить на множестве п вершин, определяется как N = n n -1 . При n = 10 имеем 10 8 различных деревьев, но из них только106 неизоморфны. Неизоморфные деревья считаются существенно различными. Примеры деревьев приведены на рис. 2.23. Любое дерево G c n вершинами можно описать упорядоченной последовательностью n- 1 номеров вершин a ( G ) = ( a 1 , a 2 . a n — 1 ) , которая называется символом дерева . Запись символа для данного дерева осуществляется следующим образом: 1. Осуществляется нумерация вершин дерева. 2. Выбирается концевая (или висячая) вершина с наименьшим номером и в последовательность α( G ) записывается номер α 1 смежной с ней вершины, а сама концевая вершина удаляется из последовательности вместе с ребром. 3. Процесс повторяется, причем через n -2 шагов от дерева остается одно ребро, положение которого определяется парой номеров вершин. Рис. 2.23 38

Для дерева G 1 , изображенного на рис. 2.23, а, a ( G 1 ) = (2, 2, 2,5,5,7) , а для дерева G 2 на рис. 2.23, б, a ( G 2 ) = (2,3, 4,3, 4,7,7, 7) . Если известен символ дерева, то построение дерева по его символу осуществляется в следующей последовательности: 1. Записывается множество номеров вершин дерева N =<1,2. n >. 2. Из множества N выбирается наименьший номер a min , который отсут- ствует в a ( G ) и строится ребро ( a min , a 1 ). 3. Из множества N удаляется номер a min , а из множества a ( G ) удаляется номер a 1 , и процесс продолжается до исчерпывания символа a ( G ) . В последовательности N остается пара вершин, которая определяет последнее ребро дерева.

2.9. Покрывающее дерево связного графа. Экстремальное дерево

Покрывающим деревом связного графа называется любое дерево, связывающее все его вершины и имеющее в качестве ветвей ребра этою графа.

На рис. 2.24 приведен связный
граф и одно из его покрывающих дере-	1	2
вьев. Число различных покрывающих
деревьев графа без петель определяется	5
теоремой Трента. В графе G без петель

с n вершинами число L различных де-	3
ревьев равно минору любого из элемен-		4

тов главной диагонали квадратной матрицы В порядка n . Матрица В строится следующим образом: на главной диагонали записываются степени вершин графа, а ij -й и ji -й элементы равны взятому со знаком минус числу ребер, связывающих вершины i и j . Для графа на рис. 2.24 матрица В имеет вид

é 3		— 1	— 2	0	0	ù	é 3 — 2 0			0 ù
ê — 1 4			— 1	— 1	— 1 ú
ê	ú	L = D 22	ê — 2 4		— 1	0 ú
B = ê — 2			— 1 4		— 1	0	ú ,	= ê	— 1	5	ú = 76 .
ê 0	— 1 — 1			5	— 3 ú		ê 0	— 3 ú
							ê 0	0	— 3 4 ú
ê	— 1	0	— 3 4		ú	ë	û
ë 0					û

В ряде случаев, например, при анализе цепей и систем возникает необходимость получить все покрывающие деревья графа. Рассмотрим один из алгоритмов решения этой задачи на примере. Пример 2.5. Найти все покрывающие деревья графа на рис. 2.25. 39

Источник

2.6. Операции над графами

2.7. Задача о кратчайшем пути связного неориентированного графа

Дан неориентированный граф G ( X , Г ), каждому ребру v = ( x i , x j ) которого приписано некоторое число l ( v ) ³ 0 , называемое длиной ребра. При этом любая

цепь μ будет характеризоваться длиной l ( m ) = å l ( v ) .	Требуется среди всех
v Î V
возможных путей между произвольными вершинами x i	и x j найти такой, что-

бы его полная длина была наименьшей. Рассмотрим алгоритм определения кратчайшего пути, использующий индексацию вершин графа. 1. Каждая вершина х к рассматриваемого графа должна быть помечена индексом λ к . Конечной вершине х j первоначально присваивается индекс λ j =0. 2. На следующем шаге двигаемся от конечной вершины по инцидентным ребрам в сторону начальной вершины х i . Вторым вершинам этих ребер присваивается индекс λ j , численно равный длине ребра l ( х j х i ) от конечной точки до данной. 3. От каждой оцифрованной вершины двигаемся по инцидентным ребрам в сторону начальной вершины и вторым их концам присваиваем индексы, численно равные сумме величины индекса предыдущей вершины и длины данного ребра графа: l n = l 1 + l ( x 1 , x n ) . К каждой вершине можно подойти нескольки- ми путями, поэтому осуществляется процесс замены индексов, т. е. для каждой вершины следует найти такой индекс, который был бы наименьшим. Процедура продолжается, пока не будет оцифрована начальная вершина х i . Индекс λ i начальной вершины будет равен длине кратчайшего пути. 4. Кратчайший путь будет проходить через вершины х к , х n , начиная с х i , разность индексов которых λ k — λ n численно равна длине ребра. 37

В качестве примера рас-				B	0
смотрим граф,		приведенный		9	9
на рис. 2.22.	3
		3
Ребрам			графа приписаны			4
	8
		числа, которые					в	условных	13	5	4	7
единицах				соответствуют их									4
	длине. Нужно найти кратчай-						3	6		7
ший путь между вершинами А				7	2	7
и В . Индексы вершин			записа-	7	1	5
ны в кружочках. Кратчайший					A	9
				10
путь выделен на рисунке жир-

ной линией. Рис. 2.22

2.8. Деревья. Символ дерева

Деревом называется конечный связный неориентированный граф, не имеющий циклов. Деревья обладают следующими свойствами: 1) любые две вершины дерева связаны простой цепью; 2) дерево с n вершинами имеет n- 1 ребер; 3) число N различных деревьев, которые можно построить на множестве п вершин, определяется как N = n n -1 . При n = 10 имеем 10 8 различных деревьев, но из них только106 неизоморфны. Неизоморфные деревья считаются существенно различными. Примеры деревьев приведены на рис. 2.23. Любое дерево G c n вершинами можно описать упорядоченной последовательностью n- 1 номеров вершин a ( G ) = ( a 1 , a 2 . a n — 1 ) , которая называется символом дерева . Запись символа для данного дерева осуществляется следующим образом: 1. Осуществляется нумерация вершин дерева. 2. Выбирается концевая (или висячая) вершина с наименьшим номером и в последовательность α( G ) записывается номер α 1 смежной с ней вершины, а сама концевая вершина удаляется из последовательности вместе с ребром. 3. Процесс повторяется, причем через n -2 шагов от дерева остается одно ребро, положение которого определяется парой номеров вершин. Рис. 2.23 38

Для дерева G 1 , изображенного на рис. 2.23, а, a ( G 1 ) = (2, 2, 2,5,5,7) , а для дерева G 2 на рис. 2.23, б, a ( G 2 ) = (2,3, 4,3, 4,7,7, 7) . Если известен символ дерева, то построение дерева по его символу осуществляется в следующей последовательности: 1. Записывается множество номеров вершин дерева N =<1,2. n >. 2. Из множества N выбирается наименьший номер a min , который отсут- ствует в a ( G ) и строится ребро ( a min , a 1 ). 3. Из множества N удаляется номер a min , а из множества a ( G ) удаляется номер a 1 , и процесс продолжается до исчерпывания символа a ( G ) . В последовательности N остается пара вершин, которая определяет последнее ребро дерева.

2.9. Покрывающее дерево связного графа. Экстремальное дерево

Покрывающим деревом связного графа называется любое дерево, связывающее все его вершины и имеющее в качестве ветвей ребра этою графа.

На рис. 2.24 приведен связный
граф и одно из его покрывающих дере-	1	2
вьев. Число различных покрывающих
деревьев графа без петель определяется	5
теоремой Трента. В графе G без петель

с n вершинами число L различных де-	3
ревьев равно минору любого из элемен-		4

тов главной диагонали квадратной матрицы В порядка n . Матрица В строится следующим образом: на главной диагонали записываются степени вершин графа, а ij -й и ji -й элементы равны взятому со знаком минус числу ребер, связывающих вершины i и j . Для графа на рис. 2.24 матрица В имеет вид

é 3		— 1	— 2	0	0	ù	é 3 — 2 0			0 ù
ê — 1 4			— 1	— 1	— 1 ú
ê	ú	L = D 22	ê — 2 4		— 1	0 ú
B = ê — 2			— 1 4		— 1	0	ú ,	= ê	— 1	5	ú = 76 .
ê 0	— 1 — 1			5	— 3 ú		ê 0	— 3 ú
							ê 0	0	— 3 4 ú
ê	— 1	0	— 3 4		ú	ë	û
ë 0					û

В ряде случаев, например, при анализе цепей и систем возникает необходимость получить все покрывающие деревья графа. Рассмотрим один из алгоритмов решения этой задачи на примере. Пример 2.5. Найти все покрывающие деревья графа на рис. 2.25. 39

Источник