Главная / Графы и их применение / Что называется совершенным паросочетанием в двудольном графе G(V1V2)?

Что называется совершенным паросочетанием в двудольном графе G(V1V2)?

вопрос

Правильный ответ:

совершенным паросочетанием из V1 в V2 в двудольном графе G(V1,V2) называется взаимно однозначное соответствие между вершинами из V1 и подмножеством вершин из V2, обладающее тем свойством, что соответствующие вершины соединены ребром
совершенным паросочетанием из V1 в V2 в двудольном графе G(V1V2) называется (V(G),E(G), где V(G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами. Употребление слова "семейство" говорит о том, что допускаются кратные ребра. Будем называть V(G) множеством вершин, а E(G) - семейством ребер графа G. О каждом ребре вида {v,w} говорят, что оно соединяет вершины v и w. Каждая петля {v,v} соединяет вершину v саму с собой
совершенным паросочетанием из V1 в V2 в двудольном графе G(V1,V2) называется D(V(D),A(D), где V(D) непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами). Дуга, у которой вершина v является первым элементом, а вершина - вторым, называется дугой из v в w. Заметим, что дуги {v,w} и {w,v} различны. Хотя графы и орграфы – различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги
допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-либо вершиной из V2 графа G, тогда совершенным паросочетанием из в называется взаимно однозначное соответствие между вершинами из V1 и подмножеством вершин из V2
Сложность вопроса
33
Сложность курса: Графы и их применение
81
Оценить вопрос
Очень сложно
Сложно
Средне
Легко
Очень легко
Комментарии:
Аноним
Я провалил сессию, почему я не углядел данный сайт с всеми ответами по интуит в начале сессии
29 ноя 2016
Оставить комментарий
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.