Шарифов Ф. А.
Совершенные паросочетания и расширенный полиматроид

Зазначено, що у відомих алгоритмах розв'язування задачі про призначення в явному вигляді чи опосередковано використовуються відомі класичні умови існування перфектного паросполучення в дводольному графі. Показано, що кожному дводольному графу можна співставити деякий вектор і розширений поліматроїд таким чином, що даний вектор є базою цього розширеного поліматроїда тоді та тільки тоді, коли даний граф містить перфектие паросполучення.

PDF

Бібліографічний опис:
Шарифов Ф. А.  Совершенные паросочетания и расширенный полиматроид. Кибернетика и системный анализ. 2008. Т. 44, № 3. С. 173-179. URL: http://jnas.nbuv.gov.ua/article/UJRN-0000029585