RUSSIAN

Паросочетания и смежные задачи (графы)

By Мирзаянов М.Р.

Book information

Language
russian
Format
DOC
Filesize
1 MB (1186304 bytes)
Pages
\0
Library
twirpx
Time added
2017-08-07 07:01:42
Информатика и вычислительная техника;Методы програ

Description

Определения и вводные понятия. Критерий Кенига.Четыре основные задачи.Эквивалентность задач: MM и MEC, MIVS и MVC.Эквивалентность задач: MM и MVC для двудольных графов. Матричная теорема Кенига. Построение максимального паросочетания в двудольном графе. Алгоритм построения максимального паросочетания. Алгоритм Куна. Модифицированный алгоритм Куна. Эвристический алгоритм нахождения максимального паросочетания.Построение минимального вершинного покрытия в двудольном графе. Алгоритм нахождения минимального вершинного покрытия.

Similar books