игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Графы и их применение / Тест 15

Графы и их применение - тест 15

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

Ответ:

 (1) совершенным паросочетанием из V1 в V2 в двудольном графе G(V1,V2) называется взаимно однозначное соответствие между вершинами из V1 и подмножеством вершин из V2, обладающее тем свойством, что соответствующие вершины соединены ребром 

 (2) совершенным паросочетанием из 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 саму с собой 

 (3) совершенным паросочетанием из V1 в V2 в двудольном графе G(V1,V2) называется D(V(D),A(D), где V(D) непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами). Дуга, у которой вершина v является первым элементом, а вершина - вторым, называется дугой из v в w. Заметим, что дуги {v,w} и {w,v} различны. Хотя графы и орграфы – различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги 

 (4) допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-либо вершиной из V2 графа G, тогда совершенным паросочетанием из в называется взаимно однозначное соответствие между вершинами из V1 и подмножеством вершин из V2 

Номер 2 
Какой граф называется двудольным?

Ответ:

 (1) бесконечный граф, все вершины которого имеют конечные степени 

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

 (3) если существует разомкнутая цепь, проходящая через все вершины графа степени 1, то такой граф называется двудольным 

 (4) допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-либо вершиной из V2, тогда G называем двудольным графом 

Номер 3 
Какой граф называется полным двудольным графом?

Ответ:

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

 (2) если граф имеет четное число циклов, то такой граф называется полным двудольным графом 

 (3) если граф имеет четное число мостов, то такой граф называется полным двудольным графом 

 (4) следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из V1 соединена с каждой вершиной из V2; если же это так и если при этом граф G простой, то он называется полным двудольным графом и обычно обозначается Km,n, где m,n - число вершин, соответственно, в V1 и V2 

Упражнение 2:
Номер 1 
Что называется латинским прямоугольником?

Ответ:

 (1) латинским (m×n)- прямоугольником называется (m×n) - матрица M=(mij), элементами которой являются целые числа, удовлетворяющие условиям (1) 1≤mij≤n, (2) все элементы в каждой строке и в каждом столбце различны. Заметим, что из условий (1) и (2) следует, что m≤n 

 (2) прямоугольная матрица, состоящая из реберно-хроматических чисел графа G, называется латинским прямоугольником 

 (3) прямоугольная матрица, состоящая из степеней вершин графа G, называется латинским прямоугольником 

 (4) прямоугольная матрица, состоящая из весов графа G, называется латинским прямоугольником 

Номер 2 
Что называется латинским квадратом?

Ответ:

 (1) если два графа имеют общую вершину или ребро, то их называют латинским квадратом 

 (2) квадратная матрица, образованная ребрами бесконечного графа G называется латинским квадратом 

 (3) квадратная матрица, образованная компонентами связного графа G, называется латинским квадратом 

 (4) латинским (m×n) - квадратом называется (m×n) - матрица M=(mij), элементами которой являются целые числа, удовлетворяющие условиям (1) 1≤mij≤n, (2) все элементы в каждой строке и в каждом столбце различны, если m=n 

Номер 3 
Можно ли латинский прямоугольник расширить до латинского квадрата?

Ответ:

 (1) да, если взять m=n и выполнить условие 1≤mij≤n 

 (2) нет 

 (3) да, если взять m≥n и выполнить условие 1≤mij≤n 

 (4) да, если взять m≥n и выполнить условие 1≥mij≥n 

Упражнение 3:
Номер 1 
Можно ли получить двудольный граф соединением двух графов Km,n=Nm+Nn?

Ответ:

 (1) да, можно 

 (2) нет, нельзя 

 (3) нельзя, если m≥n 

 (4) нельзя, если m=n 

Номер 2 
Можно ли операции объединения и соединения распространить на любое конечное число графов?

Ответ:

 (1) да 

 (2) нет 

 (3) да, только на четное число графов 

 (4) да, только на нечетное число графов 

Номер 3 
Операции объединения и соединения графов коммутативны и ассоциативны?

Ответ:

 (1) да, операции объединения и соединения коммутативны и ассоциативны 

 (2) нет, операции объединения и соединения не коммутативны и не ассоциативны 

 (3) операции объединения и соединения графов коммутативны, но не ассоциативны 

 (4) операции объединения и соединения графов не коммутативны, но ассоциативны 



Главная / Алгоритмы и дискретные структуры / Графы и их применение / Тест 15