|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
02.03.2011, 02:43 | #1 |
Регистрация: 02.03.2011
Сообщений: 3
|
дискретка и сишарп
Список задач повышенной вычислительной сложности
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 по изоморфной подстановке 1 3 5 4 2 1 Пример выдачи результата в файл OUTPUT.TXT по изоморфному вложению 1 - 5 - 2 1 Пример выдачи результата в файл OUTPUT.TXT по орбитам группы (1 3 4)(6)(2 5) 1 3 1 1 3 2 Пример представления результата в файле DESCR.TXT Graph name: G-1 Graph orbits: (1 2 3)(4) ___________________________________ __________________________ Это бонусные задания по дискретке.18 пунктов-сами задания.как это реализовать на проге не имею понятия.из этих заданий достаточно решить 2-3.если есть какие-то идеи или уже готовый вариант,сильно выручите. Последний раз редактировалось иваневрейтор; 02.03.2011 в 02:50. |
08.03.2011, 23:29 | #2 |
Форумчанин
Регистрация: 24.04.2008
Сообщений: 300
|
и что ты хочешь?чтобы за тебя решили?тогда во фриланс.Задача 500р.Итого 1000-1500.Срок неделя.Icq 456 946 681
Последний раз редактировалось bondik; 08.03.2011 в 23:31. |
09.03.2011, 00:21 | #3 |
Регистрация: 02.03.2011
Сообщений: 3
|
спасибо.уже более менее разобрался с двумя задачами и похожими на них(1 и 7).но понять решение остальных пока не могу
Последний раз редактировалось иваневрейтор; 09.03.2011 в 01:02. |
25.03.2011, 21:28 | #4 |
Новичок
Джуниор
Регистрация: 25.03.2011
Сообщений: 1
|
парень, можешь скинуть то,что ты разобрал?? плз )) кстати,в каком вузе учишься?
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Дискретка | Снс | Помощь студентам | 0 | 29.09.2010 11:48 |
дискретка | elka | Помощь студентам | 0 | 25.01.2010 22:08 |