Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.63/49: Рейтинг темы: голосов - 49, средняя оценка - 4.63
0 / 0 / 0
Регистрация: 03.03.2011
Сообщений: 6
1

C# и Теория Графов

03.03.2011, 14:41. Просмотров 9820. Ответов 5
Метки нет (Все метки)

Собственно нужно решить пару задачек из дискретной математики, я даже представления не имею как это делать на C#.

Задачки под катом. Если кто-нибудь поможет, буду очень благодарен.

задачи
Тексты исходных модулей должны быть хорошо документированы внутренними
комментариями. Присылайте тексты исходных модулей, exe-модули (или DLL-
библиотеки) и тестовые орграфы или ордеревья с результатами вычислений на них.
Тестов должно быть не менее 10. Отчет должен содержать инструкцию к запуску и
описание основной сути работы алгоритма на примере и ограничения на размер орграфов
(ордеревьев) с указанием причины ограничения. Строго соблюдать форму представления
исходных орграфов (файл INPUT.TXT) и вида результата (файл OUTPUT.TXT или файл
DESCR.TXT).
1. Для ордерева определить все его автоморфные подстановки.
2. Для ордерева определить орбиты вершинной группы автоморфизмов. Результат –
номер орбиты для каждой вершины ордерева.
3. Для ордерева определить число симметрии ордерева.
4. Для двух ордеревьев определить их изоморфизм и все изоморфные подстановки G1
на G2. Результат 0, если нет изоморфизма.
5. Определить все изоморфные вложения первого ордерева во второе ордерево.
Результат 0, если нет вложения.
6. Определить одно изоморфное вложение первого ордерева во второе ордерево.
Результат 0, если нет вложения.
7. Найти одно максимальное общее поддерево для двух ордеревьев.
8. Найти все максимальные общие поддеревья для двух ордеревьев.
9. Для заданного ордерева определить все его поддеревья. Результат – число
поддеревьев.
10. Для заданного ордерева определить все его поддеревья. Результат – матрица
смежности вершин для каждого поддерева.
11. Для заданного ордерева определить вектор-индекс сложности в базисе всех
полупутей с числом вершин от 1 до 4 включительно (ISC(G/P0)=1, ISC(G/P1)=3).
Полупуть – цепь с различной ориентацией дуг этой цепи.
12. Для заданного ордерева определить вектор-индекс сложности в базисе всех путей
(ISC(G/P0)=1, ISC(G/P1)=3).
13. Для заданного орграфа определить вектор-индекс сложности в базисе всех путей
(ISC(G/P0)=1, ISC(G/P1)=3).
14. Для заданного орграфа определить вектор-индекс сложности в базисе всех
полупутей с числом вершин от 1 до 4 включительно (ISC(G/P0)=1, ISC(G/P1)=3).
15. Для заданных двух орграфов определить изоморфную подстановку, если они
изоморфны и выдать результат 0, если не изоморфны.
16. Для заданных двух орграфов G1 и G2 определить изоморфное вложение G2 в G1.
Результат, либо подстановка вложения G2 в G1, либо 0.
17. Для заданных двух орграфов G1 и G2 определить их максимальный общий
подграф. Результат – подстановка вершин подграфа G1 на вершины подграфа G2.
18. Для заданных двух орграфов G1 и G2 определить их максимальный общий
фрагмент. Результат – подстановка вершин фрагмента G1 на вершины фрагмента
G2.

Входной файл для графа или пары графов имеет имя INPUT.TXT. Для изоморфизма,
изоморфного вложения и максимального изоморфного пересечения два орграфа
подряд в одном файле INPUT.TXT.
Выходной файл с результатами в произвольной форме имеет имя DESCR.TXT
Стандартный выходной файл имеет имя OUTPUT.TXT и в качестве результатов может
быть в этом файле следующее:
• число (например, индекс сложности, число поддеревьев ордерева и др.);



нижняя часть подстановки, т.е. номера вершин через пробел (для изоморфизма
и изоморфного вложения и изоморфного пересечения). Если вершина не имеет
отображения то символ – ;
число вершин и матрица смежности вершин графа-результата;
граф или 2 графа, заданные, F0-представлением;
число 0, если нет изоморфизма или изоморфного вложения.





Пример задания орграфа матрицей смежности вершин в файле INPUT.TXT
12
010000000001
101000000001
010100000000
001011000000
000101000000
000110100000
000001010000
000000101100
000000010100
000000011010
000000000101
110000000010

Пример1 задания графа F0-представлением в файле INPUT.TXT

1- имя или номер орграфа
5 5 0 4 0 2 4 0 2 0 4 2 0
*
Матрица смежности вершин для графа в F0-представлении Примера1
5
00001
00010
01010
01000
01010
Пример2 задания графа F0-представлением в файле INPUT.TXT

1-циклический граф [9;6]-10
9 2 6 0 1 3 0 2 4 7 0 3 5 0 4 6 0 1 5 8
9 0 3 0 6 0 6 0
*
Пример выдачи результата в файл OUTPUT.TXT
2
Пример выдачи результата в файл OUTPUT.TXT по изоморфной подстановке
135421
Пример выдачи результата в файл OUTPUT.TXT по изоморфному вложению
1-5-21
Пример выдачи результата в файл OUTPUT.TXT по орбитам группы (1 3 4)(6)(2 5)
131132
Пример представления результата в файле DESCR.TXT
Graph name: G-1
Graph orbits:
(1 2 3)(4)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.03.2011, 14:41
Ответы с готовыми решениями:

Теория графов. Обод
Определение. Обод – это граф, вершины которого V0,V1,…,Vn (n>=2) можно занумеровать так, что для...

Теория графов. Алгоритм перестановки
Добрый вечер! Столкнулся с проблемой. Не могу понять, как реализовать алгоритм перебора. Задача...

Теория графов
Выписать все образующие циклической группы < а> порядка 12 Весь семестр отдыхал, а теперь вот...:(...

Теория графов
Есть задание. найти максимальное и среднее расстояние между центральными вершинами...

5
580 / 367 / 63
Регистрация: 22.07.2009
Сообщений: 875
Записей в блоге: 4
03.03.2011, 17:23 2
Цитата Сообщение от samdman Посмотреть сообщение
Собственно нужно решить пару задачек из дискретной математики, я даже представления не имею как это делать на C#.

Задачки под катом. Если кто-нибудь поможет, буду очень благодарен.
C# не самый лучший язык для деятельности подобного рода.
В С++ есть хороший иструмент - BGL(Boost Graph Library). Когда-то у меня даже книга была на Русском.
Если уж так нужен С# - я бы собирал алгоритмы из BGL на С++ в dll и юзал через PInvoke....
1
811 / 702 / 110
Регистрация: 06.10.2010
Сообщений: 825
Записей в блоге: 1
04.03.2011, 11:03 3
Есть такая открытая библиотека: http://ngenerics.codeplex.com/. В ней есть много структур различных деревьев, графов и алгоритмы работы с ними.
Ещё очень хорошо про это всё написано здесь: http://rain.ifmo.ru/cat/view.php/theory. С примерами.
PS. Задачек под катом не парочка, а почти 20.
1
0 / 0 / 0
Регистрация: 03.03.2011
Сообщений: 6
04.03.2011, 15:09  [ТС] 4
дело в том, что мне нужно решить только пару из них)
0
183 / 186 / 17
Регистрация: 26.11.2010
Сообщений: 511
04.03.2011, 21:25 5
Цитата Сообщение от samdman Посмотреть сообщение
дело в том, что мне нужно решить только пару из них)
Тем не менее лучше решать самому, так как задачи не обязательные, на первом курсе-то сложновато небось.
0
0 / 0 / 0
Регистрация: 03.03.2011
Сообщений: 6
24.03.2011, 22:13  [ТС] 6
9. Для заданного ордерева определить все его поддеревья. Результат – число
поддеревьев.

Ну вот конкретно для этой задачи, ввод можно сделать через матрицу смежности. Можно использовать Алгоритм Брона-Кербоша, но как его переделать под ордеревья? Подскажите пожалуйста, всё перерыл, нигде найти не могу.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.03.2011, 22:13

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

теория графов
помогите пожалуйста

Теория графов
Вот помогите, пожалуйста, кто чем сможет, я уже запутался конкретно. Задание первого рисунка: Найти...

Теория графов
Прошу помощи Правила форума, пункт 5.18. Запрещено размещать задания и решения в виде картинок...

Теория графов
Проверьте пожалуйста правильно ли я объединил графы?)

Теория графов
Здравствуйте уважаемые форумчане, помогите справиться с такой задачкой по теории графов: Сумма...

теория графов
кто-то знает решение этой задачи......дан неориентированый граф.Показать что каждое максимальное...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.