Новость из категории: Информация

Поиск паросочетаний графов с помощью T-SQL. Часть IV

Содержание:
1. Часть I;
2. Часть II ;
3. Часть III;
4. Часть IV (Вы читаете данный раздел).
Дополнительно о принципах и терминах

Поиск паросочетаний графов с помощью T-SQL. Часть IV

Продолжим наше знакомство с принципами и терминологией графов. На этот раз обратимся к проблеме паросочетания графов. На рисунке ниже приведены примеры, иллюстрирующие некоторые концепции. M1, M2, M3 и M4 представляют различные подмножества ребер из G. Для некоторых Mn ребра, уникальные для G, представлены тонкими серыми линиями, а ребра, общие для G и Mn, показаны толстыми зелеными линиями.

Поиск паросочетаний графов с помощью T-SQL. Часть IV
Примеры паросочетаний графов

Паросочетание. Паросочетание М в графе G — подмножество ребер G, в котором никакие два ребра не имеют общей вершины. На рисунке выше M1, М3 и М4 — паросочетания в G, но не М2, так как имеется два ребра с общей вершиной В.

Наибольшее паросочетание. Паросочетание М в графе G является наибольшим паросочетанием, если нельзя добавить больше ребер из G, которых еще нет в М, к М. На рисунке выше как М3, так и М4 — наибольшее паросочетание. M1 — паросочетание, но не наибольшее, так как вы можете добавить вершину (С, 4).

Паросочетание максимальной мощности. Паросочетание М в графе G является паросочетанием максимальной мощности, если имеет самое большое возможное число ребер. Каждое паросочетание максимальной мощности — наибольшее, но не всякое наибольшее паросочетание является паросочетанием максимальной мощности. На рисунке выше М4 — паросочетание максимальной мощности, но М3 — нет. Это не распространяется на данные примера графа G, но для каждого графа может существовать несколько различных паросочетаний максимальной мощности.

На данном этапе приведенное выше описание задачи поиска паросочетаний должно стать для вас совершенно очевидным: эта задача известна как поиск паросочетания максимальной мощности (М) в невзвешенном двудольном графе (G).

Поиск паросочетаний графов с помощью T-SQL. Часть IV
Типы путей

На рисунке выше представлены дополнительные иллюстрации, чтобы помочь понять определенные типы путей в графах.

Связанная вершина. Для данного паросочетания М в графе G связанная вершина является вершиной, которая принадлежит ребру в М.

Свободная вершина. Для данного паросочетания М в графе G свободная вершина является вершиной, которая не принадлежит никакому ребру в М.

Поиск паросочетаний графов с помощью T-SQL. Часть IV

Чередующийся путь. Чередующийся путь представляет собой путь, который состоит из ребер в паросочетании и не в паросочетании. Оба пути на рисунке выше представляют собой чередующиеся пути.


Вы далеки от IT и тема данной статьи вас совершенно не интересует. Гораздо более важной темой для вас является поиск поставщика пластиковой тары для вашего производственного предприятия. И именно поэтому я настоятельно рекомендую вам заглянуть на http://www.pettara.ru/. Здесь вы найдете то, что искали, и сможете заключить договор на поставку необходимой вам продукции на самых выгодных для себя условиях.

Рейтинг статьи

Оценка
0/5
голосов: 0
Ваша оценка статье по пятибальной шкале:
 
 
   

Поделиться

Перевести статью:

Похожие новости

Комментарии

Информация

^ Наверх