симметрической разности
симметрической разности получаются циклы (вырожденный случай). Исследовательская работа - разработать программу нахождения всех циклов графа.
3.6. Кратчайшие пути
3.6.1. Постановка задачи. Вывод пути
Постановка задачи. Дан ориентированный граф G=<V,E>, веса дуг - А[i,j] (i,j=1..N, где N - количество вершин графа), начальная и конечная вершины - s, t?V. Веса дуг записаны в матрице смежности A, если вершины i и j не связаны дугой, то A[i,j]=?. Путь между s и t оценивается ? A[i,j]. Найти путь с минимальной оценкой. i,j?пути
Пример.
Кратчайший путь из 1 в 4 проходит через 3-ю и 2-ю вершины и имеет оценку 6.
Особый случай - контуры с отрицательной оценкой.
Пример.
При s=1 и t=5, обходя контур 3?4? 2? 3 достаточное число раз, можно сделать так, что оценка пути между вершинами 1 и 5 будет меньше любого целого числа. Оценку пути назовем его весом или длиной. Будем рассматривать только графы без контуров отрицательного веса.
Нам необходимо найти кратчайший
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
