Автор работы: Пользователь скрыл имя, 22 Декабря 2010 в 10:53, курсовая работа
В первой части курсовой работы рассматривается вопрос о связности графов. Понятия вершинной и реберной связности широко применяются в прикладных задачах теории графов. Рассмотрим одну математическую модель, возникающую, в частности, при проектировании и анализе сетей ЭВМ. Имеется сеть, состоящая из центров хранения и переработки информации. Некоторые пары центров соединены каналами. Обмен информацией между любыми двумя центрами осуществляется либо непосредственно по соединяющему их каналу, если он есть, либо через другие каналы и центры. Сеть считается исправной, если каждая пара центров в состоянии обмениваться информацией. Такой сети естественно сопоставить граф: вершины – центры, ребра – каналы сети. Тогда исправной сети будет соответствовать связный граф. Важным понятием является надежность (живучесть) сети, под которой обычно подразумевают способность сети функционировать при выходе из строя одного или нескольких центров или (и) каналов. Ясно, что менее надежной следует считать ту сеть, исправность которой нарушается при повреждении меньшего количества элементов. Оказывается, надежность сети можно измерять на основе вводимых ниже определений.
Во второй части работы, практической, приводится описание программного средства, предназначенного для поиска двусвязных компонент в графах и определения связности.
Введение
1 Теоретическая часть
1.1 Основные понятия теории графов
2 Транспортная задача
2.1Основные понятия.
2.2Алгоритм поиска в ширину
2.3 Увеличение потока (или Алгоритм Форда-Фалкерсона)
2.4 Алгоритм Беллмана-Форда
Список использованной литературы
Приложение.Текст задачи
while( neg_cycle != MAX_VAL )
{
v = neg_cycle; u = pred[v];
do
{
add = min(add, C[u][v]-F[u][v]);
v = u; u = pred[v];
}
while( v != neg_cycle );
v = neg_cycle; u = pred[v];
do
{
F[u][v] += add;
F[v][u] -= add;
v = u; u = pred[v];
}
while( v != neg_cycle );
neg_cycle = bf(t);
}
for(int u = 1; u < N; u++)
for(int v = 1; v < N; v++)
if( F[u][v] > 0 )
min_cost += F[u][v] * P[u][v];
}
void file_write()
{
out << max_flow << endl;
out << min_cost << endl;
}
void main()
{
file_read();
min_cost_flow();
file_write();
}
Информация о работе Нахождение минимальной стоимости в транспортной сети