Задачи для самостоятельного решения

↑

⇐ ПредыдущаяСтр 3 из 11Следующая ⇒

Задачи для самостоятельного решения

1. Найти кратчайший путь от вершины x₁ до вершины x₇ в следующих графах:

a)     

2. Найти кратчайшие расстояния от вершины x₁ до всех остальных вершин в следующих графах:

a)

b)

3. Для графов примеров 1 a), 1 b) найти кратчайшие расстояния от вершины x₂ до всех остальных вершин.

4. Определить кратчайшие расстояния между каждой парой вершин для графов со следующими матрицами расстояний:

a)          b)

c)   d)

3. ПОТОКИ В СЕТЯХ

Пусть каждой дуге  графа  поставлено в соответствие положительное число , интерпретируемое как пропускная способность дуги. Зафиксируем две вершины . Вершину s назовем источником, а вершину t − стоком.

Стационарным потоком величины  из вершины s в вершину  на сети  называется функция , заданная на всех дугах и удовлетворяющая следующим условиям:

                                                     (1)

                                         (2)

Здесь .  

Условия (1) означают, что поток по каждой дуге не должен превышать ее пропускную способность. Условия (2) показывают, что для источника  суммарное количество входящего и выходящего потока должно быть равно  – величине потока в сети. Аналогично для стока  суммарное количество выходящего и входящего потока также равно . Для всех промежуточных вершин сети должно выполняться равенство .

В сети с пропускными способностями дуг  всегда существует стационарный поток (например, величины 0), причем не единственный.

Познавательные статьи:



Психологические особенности спортивного соревнования

Приготовление дезинфицирующих растворов различной концентрации

Занятость населения и рынок труда

Социальный статус семьи и её типология