Паросочетание

Паросочетание

В теории графов, паросочетание или независимое множество ребер в графе — это набор попарно несмежных ребер.

Определение

Пусть дан граф G = (V,E), паросочетание M в G это множество попарно несмежных ребер, то есть ребер, не имеющих общих вершин.

Maximal-matching.svg

Максимальное паросочетание — это такое паросочетание, которое не содержится ни в каком другом паросочетании этого графа.
Наибольшее паросочетание — это такое паросочетание, которое содержит максимальное количество ребер.

Алгоритмы

Заготовка раздела
 Этот раздел не завершён.
Вы поможете проекту, исправив и дополнив его.

Алгоритм поиска максимального паросочетания в двудольном графе

Ссылки


Формула

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Полезное


Смотреть что такое "Паросочетание" в других словарях:

  • Венгерский алгоритм — Венгерский алгоритм  алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время (см. исследование операций). Он был разработан и опубликован Харолдом Куном в 1955 году. Автор дал ему имя «венгерский метод» в связи с тем, что …   Википедия

  • ПОКРЫТИЯ И УПАКОВКИ — комбинаторные конфигурации, связанные с многозначным отображением одного множества на другое. Пусть заданы множества Vи Еи многозначное отображение Г множества Ена множество V. Пусть Г(е). образ элемента при отображении Г и для любого пусть Г(С) …   Математическая энциклопедия

  • Линейное программирование — Линейное программирование  математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Линейное программирование… …   Википедия

  • МАТРОИД — гиперграф специального вида. М. определяется заданием множества Vэлементов и семейства подмножеств множества У, называемых независимыми множествами, для к рых выполняются следующие аксиомы: 1) пустое множество независимо; 2) каждое подмножество… …   Математическая энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»