Аннотация:
Вводятся понятия двудольного геометрического графа и геометрического
паросочетания. Исследуются их связи с перестановками и графами перестановок,
изучаются некоторые свойства геометрических графов и паросочетании
в них. Рассматриваются различные задачи о паросочетаниях применительно
к классу двудольных геометрических графов. Представлены эффективные алгоритмы
решения этих задач. Доказывается корректность алгоритмов, обсуждаются
некоторые аспекты их реализации.
Библиогр. 2
Полный текст:
PDF файл (1393 kB)