![]() |
|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
Опции темы
![]() |
Поиск в этой теме
![]() |
![]() |
#1 |
Регистрация: 30.06.2008
Сообщений: 4
|
![]()
Даны 2 графа, они разные(в файлах в виде матрицэ смежностей), нужно сделать их одинаковыми, но при этом действий НАД ГРАФОМ должно быть совершщено как можно меньше, тоесть если разница в 2 вершины, то одну с одного удалим, одну к другому прибавим, каждое удаление, или прибавление элемента, в том числе и ребра-действие, таких действий для уравнивания нужно совершить как можно меньше.
Не могу придумать алгоритм, точнее пару придумал, но понял, что они очень несовершенны, помогите пожалуйста ![]() |
![]() |
![]() |
![]() |
#2 |
Участник клуба
Регистрация: 23.07.2007
Сообщений: 1,054
|
![]()
Вот я только что дискретную математику сдал успешно, но че то не понимаю вас.
Попробуйте перефразировать. вы говорите есть наработки? ну публикуйте, мы посмотрим. даже если это абсурд... может кого на идею наведет.
Писано по д'Эльфийски
|
![]() |
![]() |
![]() |
#3 |
Участник клуба
Регистрация: 23.07.2007
Сообщений: 1,054
|
![]()
Как я понимаю вы про метод Гаусса говорите? или что то путаю.
В этом методе используются в основном не формулы, а свое мышление. как удобнее всего преобразовать. Машину этому очень сложно научить.
Писано по д'Эльфийски
|
![]() |
![]() |
![]() |
#4 |
Регистрация: 30.06.2008
Сообщений: 4
|
![]()
Нет, не решение уравнений, у нас есть 2 графа, мы их записываем в файлы в виде матриц смежностей, считываем в матрицы в программе...
Нужно в общем сделать одинаковыми эти 2 графа, за минимальное количество изменений над каждым ГРАФОМ, где удаление или добавление любого элемента-действие. Первые мысли были о формуле-точно не так, Новые о том, что мы должны сравнить обе матрицы, выяснить сколько различий, затем по главной диагонали надписать для каждой из вершин сколько к ней подходит ребер, будут видны вершины, которые "легче" удалить, воот. Последний раз редактировалось Bashyr; 02.07.2008 в 14:40. |
![]() |
![]() |
![]() |
#5 |
Регистрация: 30.06.2008
Сообщений: 4
|
![]()
я вот думаю, что количество изменений оптимальных, точнее сумма по 2 графам=количеству разниц, тоесть если количество различий четное, то количество изменений для каждого графа оптимально-колво/2, а при нечетных не важно в каком порядке у одного (((кол-во - 1)/2)+1)
а у другого ((кол-во - 1)/2), но это только первый шаг, и даже его хз как реализовать потомучто есть такие графы, в которых кол-во ребер одинаковое, вершин разное например, и мы увидим, что разница-1, а она-3 цепь из 4 и полный из 3-пример их 3, оптимальное решение, от одного отрубить связь и вершину, и у другого связь, или у другого прибавить вершину, и отрубить связь, а у первого только вершину... |
![]() |
![]() |
![]() |
#6 |
Регистрация: 30.06.2008
Сообщений: 4
|
![]()
Все, забейте, ужо сделали.
![]() |
![]() |
![]() |
![]() |
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Математика для программиста | Gribushkino | Свободное общение | 12 | 07.01.2011 01:25 |
помогите! Дискретная математика, грамматики | tywonka | Помощь студентам | 0 | 07.06.2008 13:46 |
Математика | doniyor | Общие вопросы Delphi | 2 | 15.05.2008 18:25 |
TDateTime - математика времени | _SERGEYX_ | Общие вопросы Delphi | 2 | 14.09.2007 14:27 |
Математика в DELPHI | ironden | Общие вопросы Delphi | 2 | 17.05.2007 15:01 |