Здравствуйте очень нужна помощь, с графами столкнулся впервые. Суть такая, есть N вершин, между ними есть ребра (длину ребер  мы задаем сами целым числом). По ребрам ездят точки могут ехать в обе стороны. При нахождении 2 точек в одной вершине происходит столкновение, соответственно если точки едут по 1 ребру навстречу друг-другу тоже произойдет столкновение. Движение точек заданы списком вершин через которые они проходят. Скорости точек =1. По достижению конечной вeршины тoчка исчезает. Определить будет ли стoлкновение?
   Пишу на C# буду благодарен за любую помощь.

Моделировать с шагом 1/2, чтобы гарантированно определить столкновение навстречу движущихся по грани точек. Или проще тупо увеличить расстояния по вершинам в 2 раза, и считать время моделирование движущимся в 2 раза быстрее.
Каждая грань - пара X,Y - отсортированных по алфавиту(или порядку). Скорость на грани - +-1, в зависимости от того, из какой вершины грани начинаем движение. Таким образом, мгновенное состояние точки записывается как грань и пройденная доля грани. Для определенности ( X-Y:3/5 ) - четыре числа, если приписать длину грани для целочисленности вычислений.
Для всех точек вычисляется мгновенное состояние, совпавшие состояния означают столкновение.
С каждым шагом каждая точка в соответствии со скоростью изменяет пройденную долю до 0 или 1, после чего переводится на другую грань по маршруту движения.

В чем вообще проблемы-то?

Это сообщение отредактировал(а) ksnk - 13.12.2011, 18:49

Как реализовать множество точек и вершин? Как для каждой точки задавать маршрут?  

Grigorill, точки начинают двигаться одновременно? с целыми промежутками? с произвольными промежутками?

Двигаются одновременно у всех одна скорость =1.

А кто тут задачу задает?  
Откуда-то взялся граф и маршруты движения?

Для простоты можно считать, что сначала задается граф. В виде координат и символического обозначения точек


четырехточечный граф, где все точки соединены друг с другом. Первое вхождение точки должно сопровождаться координатами. Между точками нужно вписать длину грани. (Геометрия ни разу не эвклидова   )

Маршрут записывается как последовательность символических имен точек.

Grigorill, конвертируйте граф в двумерную матрицу, где M(i,j) = номер ребра, на котором находится i-я точка в момент времени j. Если точка находится в вершине - из двух рёбер в матрицу заносится наименьший из них.
Такая матрица легко позволяет найти "коллизии" - одновременное нахождение двух точек на одном ребре. Остаётся проверить столкновение, которое может быть только если они одновременно пришли на это ребро в одну и ту же вершину либо если они пришли на ребро с разных вершин этого ребра. Поскольку скорость = 1 и длины рёбер - целые, то при отсутствии рёбер длины 1 массив можно строить с дискретностью по времени = 1, иначе 0.5.