Page 95 - 4496

З лінійною метрикою мають справи при роботі із
друкованими платами, де зв'язок можливий тільки в точках по
взаємно перпендикулярних напрямках.
Для евклідового завдання встановлено: вершини
Штейнера мають ступінь три й розташовуються в такому
місці, що кути між інцидентними ребрами рівні 120.
Якщо простір лінійний, то в якості місць для
розташування точок Штейнера досить розглянути тільки
точки перетинання вертикальних і горизонтальних ліній, що
проходять через вершини графа. Це різко скорочує число
можливих варіантів. У прикладі для лінійного випадку
рис.3.16,у точка Штейнера – вершина 5.
3.16 Паросполучення
Паросполученням у графі називається така підмножина
його ребер, у якому ніяка пара ребер не суміжна.
Інтерес представляють два завдання, пов'язані зі
знаходженням паросочетаний. Якщо паросполучення
оцінювати числом вхідних у нього ребер, то найбільшим
називають паросполучення, що має найбільше число ребер.
Якщо ребрам приписані ваги, то максимальним
називають паросполучення, для якого сума ваг вхідних у
нього ребер максимальна.
Алгоритм знаходження найбільшого паросполучення
використовує наступні поняття.
Назвемо вершину в графові зв'язаною, якщо вона
належить паросполученню, інакше вершину назвемо вільною.
Ланцюг назвемо послідовним, якщо в ньому
послідовно повторюються ребра, що належать і не належать
паросполученню.
Якщо всі ребра паросполучення можна включити в
послідовний ланцюг, у якому початкова й кінцева вершини
вільні, то найдеться паросполучення, у якому буде число
ребер на одиницю більше. Це можливо, якщо у виділеному
ланцюзі всі ребра, що не входять у паросполучення, включити
в нього, а всі, що входять, – виключити.

92