База ответов ИНТУИТ

Графы и их применение

<<- Назад к вопросам

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

(Ответ считается верным, если отмечены все правильные варианты ответов.)

Варианты ответа
совершенным паросочетанием из V1 в V2 в двудольном графе G(V1,V2) называется взаимно однозначное соответствие между вершинами из V1 и подмножеством вершин из V2, обладающее тем свойством, что соответствующие вершины соединены ребром(Верный ответ)
совершенным паросочетанием из 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(Верный ответ)
совершенным паросочетанием из 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 саму с собой
Похожие вопросы
Что называется бесконечным в обе стороны маршрутом в графе G?
Что называется маршрутом в данном графе G(V,Е)?
Что называется путем в ориентированном графе D?
Какая вершина в ориентированном графе D называется изолированной?
Что называется бесконечным в одну сторону маршрутом в графе G?
Если в простом графе с n(≥3) вершинами ρ(v)≥n/2 для любой вершины v, то каким является граф G?
Что называется путем от v1 до v2 в графе?
Какое выражение является формулой Эйлера (здесь V - число вершин в графе, E - число ребер, а R - число граней)?
Если Е - непустое конечное множество и ϕ=(S1,...,Sm) - семейство непустых его подмножеств, то что называется трансверсалью для ϕ?
Расстоянием d(vx,vy) между вершинами графа G называем длину кратчайшего пути, их соединяющего. Наибольшее из таких d(vx,vy) называем диаметром G, наименьшее – радиусом. Может ли у какой – то вершины дерева максимальное из расстояний до других вершин равняться радиусу?