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

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

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

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

Принципы и термины

Обсуждать задачу паросочетания графов будет гораздо проще, если предварительно четко определить терминологию. Начнем с самого простого: вершин, ребер и графов.

В теории графов вершиной называется объект, который является частью набора. В нашем примере конкретный соискатель (в частности, ID А) представляет собой величину, или вершину, которая входит в набор соискателей, а конкретное рабочее место (в частности, ID 1) — величину, которая входит в набор рабочих мест.

Ребро представляет собой связь между вершинами. Например, при наличии соискателя А и рабочего места 1 ребро (А, 1) передает тот факт, что соискатель А имеет достаточную квалификацию, чтобы занять рабочее место 1.

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

Граф представляет собой набор ребер, соединяющих пары вершин. В нашем примере граф G представляет набор всех возможных ребер (соискатель, рабочее место), где соискатель квалифицирован для выполнения работы.

Графы могут иметь различные свойства, часть которых особенно интересна для нашего обсуждения: взвешенные, невзвешенные и двудольные.

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

Взвешенный или невзвешенный граф. Граф является взвешенным, если каждому ребру назначен вес. Например, иногда нужно учесть зарплату соискателя или время, которое требуется для завершения работы. Если ребрам не назначен вес, то граф — невзвешенный. Наш граф G невзвешенный, так как в настоящее время его ребрам не назначен вес.

Двудольный граф. Граф является двудольным, если каждое ребро графа соединяет какую-то вершину из двух отдельных, или непересекаюшихся, наборов. Наш граф G двудольный, так как ребра всегда связывают элемент набора соискателей с элементом набора рабочих мест. Он никогда на соединяет соискателей с соискателями или рабочие места с рабочими местами.

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

Наш двудольный граф G может быть описан как множество:
G = (X, Y, Е)
где X обозначает набор соискателей, Y — набор рабочих мест, а Е — набор ребер, представляющих связи «соискатель — рабочие места».

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

На рисунке выше показан наш граф с некоторыми образцовыми данными.


Предпочитаете работать под музыку, поэтому планируете познакомиться с принципами и терминами метода поиска паросочетаний графов с помощью T-SQL под соответствующее музыкальное сопровождение? В этом случае настоятельно советую вам заглянуть на https://vkdj.org/. Там вы сможете скачать программу ВКонтакте DJ, которая позволит вам в несколько кликов скачать свою любимую музыку из VK!

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

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

Поделиться

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

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

Комментарии

Информация

^ Наверх