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

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

Номер 1

Какой граф G называется реберно k-раскрашиваемым?

Ответ:

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

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

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

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

Номер 2

Что называется хроматическим классом?

Ответ:

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

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

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

(4) если граф G реберно k-раскрашиваем, но не является реберно (k-1)-раскрашиваемым, то k называется хроматическим классом

Номер 3

Что называется хроматическим индексом?

Ответ:

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

(2) число циклов графа

(3) число мостов графа

(4) если граф G реберно k-раскрашиваем, но не является реберно (k-1)-раскрашиваемым, то k называется хроматическим индексом

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

Номер 1

Что называется реберно-хроматическим числом графа G?

Ответ:

(1) число висячих вершин

(2) число петель в графе

(3) максимальная степень в графе

(4) если граф G реберно k-раскрашиваем, но не является реберно (k-1)-раскрашиваемым, то k называется хроматическим числом графа G

Номер 2

Какие треугольники называются сцепленными?

Ответ:

(1) если два треугольника имеют общую вершину или ребро

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

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

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

Номер 3

Сколько несцепленных треугольников с одноцветными сторонами найдется в полном графе с восемью вершинами, ребра которого окрашены в два цвета?

Ответ:

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

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

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

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

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

Номер 1

Как можно изобразить полный граф с пятью вершинами и ребрами двух цветов, если в нем не найдется треугольника с одноцветными сторонами?

Ответ:

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

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

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

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

Номер 2

Сколько одноцветных ребер имеет каждая вершина минимально у полного графа с шестью или более вершинами и ребрами двух цветов?

Ответ:

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

(2) имеет минимум два одноцветных ребра

(3) имеет минимум одно ребро

(4) не имеет ребер вообще

Номер 3

Какое минимальное число вершин имеет полный граф, ребра которого окрашены в два цвета  и который имеет хотя бы один треугольник с одинаковыми ребрами?

Ответ:

(1) в графе минимум шесть вершин

(2) в графе минимум пять вершин

(3) в графе минимум четыре вершин

(4) в графе минимум две вершины

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