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

Упражнение 1:

Номер 1

Что называется графом?

Ответ:

(1) графом G называется пара V(G), E(G), где V(G) - непустое конечное множество элементов, называемых, вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами

(2) графом G называется V(G) - непустое конечное множество элементов, называемых вершинами

(3) графом G называется E(G) - конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами

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

Номер 2

Что называется вершинами графа?

Ответ:

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

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

(3) если граф представлен парой V(G), E(G), где V(G) - непустое конечное множество элементов, называемых вершинами, а Е(G) - конечное семейство неупорядоченных пар элементов из V(G), называемых ребрами

(4) вершины представляют собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек. Точки и отрезки иначе называются вершинами

Номер 3

Что называется степенью вершины графа?

Ответ:

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

(2) степенью вершины называется число вершин в графе

(3) степенью вершины называется число ребер и вершин графа

(4) степенью или валентностью вершины v графа G называется число ребер, инцидентных v

Упражнение 2:

Номер 1

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

Ответ:

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

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

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

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

Номер 2

Что называется маршрутом в данном графе G(V,Е)?

Ответ:

(1) маршрутом в данном графе G называется конечная последовательность ребер вида {v₀,v₁},{v₁,v₂},...,{v_m-1,v_m} (обозначаемая также через v₀→v₁→v₂→...→v_m)

(2) маршрутом в графе G(V,Е) называется цепь, если все ее ребра различны

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

(4) маршрутом в графе G(V,Е) называется вершина с петлей

Номер 3

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

Ответ:

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

(2) граф называется регулярным, если у него число вершин равно числу ребер

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

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

Упражнение 3:

Номер 1

Что называется орграфом?

Ответ:

(1) орграфом D называется пара V(D),A(D), где V(D) непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами)

(2) орграфом G называется пара V(G),E(G), где V(G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G),E(G) V(G) (не обязательно различных), называемых ребрами

(3) орграфом называется такая пара, что E⊆V×V. Элементы множества E для орграфа называются дугами. Дуга в орграфе изображается линией со стрелкой, указывающей ориентацию дуги, т.е. направление от начала к концу

(4) полный ориентированный граф

Номер 2

Что называется ориентированным полным графом?

Ответ:

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

(2) полным ориентированным графом называется граф с неориентированными ребрами

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

(4) полным ориентированным графом называется граф, во всех вершинах которого имеются петли

Номер 3

Что называется путем от v₁ до v₂ в графе?

Ответ:

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

(2) путем от v₁ до v₂ в графе называется последовательность вершин от v₁ до v₂

(3) путем в графе называется число его ребер

(4) путем в графе называется петля висячей вершины

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