Главная /
Графы и их применение /
Что называется совершенным паросочетанием в двудольном графе 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
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.