дискретка и сишарп

[иваневрейтор]

Список задач повышенной вычислительной сложности

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.если есть какие-то идеи или уже готовый вариант,сильно выручите.

[bondik]

и что ты хочешь?чтобы за тебя решили?тогда во фриланс.Задача 500р.Итого 1000-1500.Срок неделя.Icq 456 946 681

[иваневрейтор]

спасибо.уже более менее разобрался с двумя задачами и похожими на них(1 и 7).но понять решение остальных пока не могу

[omgwtfgg]

парень, можешь скинуть то,что ты разобрал?? плз )) кстати,в каком вузе учишься?