ВУЗ:
Составители:
67
Задачи, возникающие в теории графов, условно можно разбить
на два класса: собственные задачи теории графов (в частности, зада-
чи подсчета числа объектов с заданными свойствами) и алгоритмы
на графах. Примером алгоритма может служить алгоритм поиска
всех путей между двумя заданными вершинами графа. Для того что-
бы иметь представление о собственных задачах
теории графов, рас-
смотрим задачу о максимальном числе аварий.
Эта задача имеет прикладное значение при трассировке печат-
ных плат. Дадим ее содержательную формулировку и решение без
доказательства. На кирпичном заводе имеется m печей и n платформ,
на которые укладываются кирпичи для транспортировки. От каждой
печи кирпичи можно перевозить вагонетками ко всем
платформам. В
местах пересечений путей вагонетки сходят с рельсов, поэтому та-
ких пересечений должно быть как можно меньше. Какое минималь-
ное число пересечений возможно, если в одной точке могут пересе-
каться не более чем два пути?
На языке теории графов эта задача формулируется следующим
образом. Пусть множество вершин графа G=<X,Y>
разбито на два
подмножества X={x
1
,x
2
,...,x
m
} и Y={y
1
,y
2
,...,y
n
} и расположено на
плоскости. Каждую вершину из Х соединим ребрами со всеми вер-
шинами Y таким образом, что ребра будут лежать в той же плоско-
сти, что и вершины из Х и Y; в каждой точке (отличной от вершин из
Х и Y) смогут пересечься только два ребра (рис. 2.35
)
Обозначим через I(m,n) мини-
мальное число пересечений.
Тогда справедливо следующее
соотношение:
1
2 m
Рис. 2.35
. . . . . . . . . . . . . . . . . . .
. . . . . . . . .
1 2 n
Страницы
- « первая
- ‹ предыдущая
- …
- 69
- 70
- 71
- 72
- 73
- …
- следующая ›
- последняя »
