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

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

Номер 1

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

Ответ:

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

(2) графом G называется пара V(G),E(G), где V(G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами. Употребление слова "семейство" говорит о том, что допускаются кратные ребра. Будем называть V(G) множеством вершин, а E(G) - семейством ребер графа G. О каждом ребре вида {v,w} говорят, что оно соединяет вершины v и w. Каждая петля {v,v} соединяет вершину v саму с собой

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

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

Номер 2

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

Ответ:

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

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

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

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

Номер 3

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

Ответ:

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

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

(3) граф, содержащий его дополнение

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

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

Номер 1

G - связный счетный граф, являющийся эйлеровым. Какими свойствами он обладает?

Ответ:

(1) в графе G нет вершин нечетной степени

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

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

(4) в графе G нет вершин четной степени

Номер 2

Какими свойствами обладает G - связный счетный граф, являющийся полуэйлеровым, но не эйлеровым?

Ответ:

(1) G содержит либо не более одной вершины нечетной степени, либо не менее одной вершины бесконечной степени

(2) для каждого конечного подграфа H графа G бесконечный граф G (описанный ранее) содержит ровно одну бесконечную компоненту

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

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

Номер 3

При каких условиях счетный граф планарен?

Ответ:

(1) G - счетный граф, каждый конечный подграф которого планарен, тогда и G планарен

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

(3) если граф G связный и все его вершины четные, то он планарен

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

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

Номер 1

Что называется бесконечным в одну сторону маршрутом в графе G?

Ответ:

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

(2) бесконечным в одну сторону маршрутом в графе G называют последовательность четных вершин

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

(4) бесконечным в одну сторону маршрутом в графе G называют маршрут, в котором все вершины имеют нечетную степень

Номер 2

Что называется  бесконечным в обе стороны маршрутом в графе G?

Ответ:

(1) бесконечная последовательность ребер вида ...,{v_-2,v_-1},{v_-1,v₀},{v₀,v_-1},{v₁,v₂},...

(2) все маршруты мультиграфа

(3) все маршруты эйлерова графа

(4) все маршруты полуэйлерова графа

Номер 3

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

Ответ:

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

(2) полуэйлеровый граф

(3) полугамильтоновый граф

(4) граф, обладающий бесконечной (двусторонней) эйлеровой цепью

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