Составители:
Рубрика:
10
n платформ
Рис.2
В местах пересечения путей вагонетки часто сходят с рельсов, поэтому
таких пересечений должно быть как можно меньше. Какое минимальное число
пересечений возможно, если в одной точке могут пересекаться не более чем два
пути.
Если обозначить через I(m,n) искомое число пересечений, то для
величины I(m,n) можно получить следующее соотношение [1]
(r
2
- r) (s
2
- s), если m=2r, n=2s;
(r
2
- r) s
2
, если m=2r, n=2s+1
I(m,n) ≥ r
2
(s
2
- s), если m=2r+1, n=2s
r
2
s
2
, если m=2r+1, n=2s+1
После знакомства в общих чертах с задачами теории графов первого
класса, приведем постановку некоторых задач второго класса, на одной из
которых - задаче о кратчайшем пути - остановимся более подробно.
§ 1.3. Алгоритмы на графах
В задачах этого класса производится поиск такой конфигурации ребер
(дуг) и вершин заданного графа, которая обладала бы некоторым оптимальным
свойством. Говоря иными словами, на графе выбирается подграф, обладающий
этим свойством. Как правило, для конечных графов эта задача принципиально
всегда разрешима. Для этого достаточно перебрать все возможные варианты и
выбрать из них наилучший в соответствующем оптимальном смысле. Однако, в
подавляющем большинстве случаев подобный перебор практически не
осуществим за любое реальное мыслимое время ввиду обилия имеющихся
возможных вариантов. Поэтому приходится изобретать алгоритмы,
уменьшающие количество перебираемых вариантов.
Приведем теперь несколько задач, связанных с практическими
проблемами, возникающими в различных областях человеческой деятельности.
Задача о минимальном остовном дереве
Страницы
- « первая
- ‹ предыдущая
- …
- 8
- 9
- 10
- 11
- 12
- …
- следующая ›
- последняя »
