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

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

Номер 1

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

Ответ:

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

(2) если его можно задать парой (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) пусть граф G не имеет петель; тогда G называется k-раскрашиваемым, если каждой его вершине можно приписать один из k цветов таким образом, чтобы никакие две смежные вершины не оказались одного цвета

Номер 2

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

Ответ:

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

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

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

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

Номер 3

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

Ответ:

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

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

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

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

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

Номер 1

Если наибольшая степень  графа равна (ρ+1)G, скольки-раскрашиваемым является граф?

Ответ:

(1) если наибольшая из степеней вершин графа G равна (ρ+1), то этот граф ρ-раскрашиваем

(2) если наибольшая из степеней вершин графа G равна (ρ+1), то этот граф (ρ+3)-раскрашиваем

(3) если наибольшая из степеней вершин графа G равна (ρ+1), то этот граф (ρ-2)-раскрашиваем

(4) если наибольшая из степеней вершин графа G равна (ρ+1), то этот граф (ρ+2)-раскрашиваем

Номер 2

Как определяем географическую карту?

Ответ:

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

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

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

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

Номер 3

Какую карту называют   k-раскрашиваемой?

Ответ:

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

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

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

(4) назовем карту k-раскрашиваемой, если она имеет k граней

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

Номер 1

Когда карта G  является 2-раскрашиваемой?

Ответ:

(1) карта G является 2-раскрашиваемой тогда и только тогда, когда G представляет собой эйлеров граф

(2) карта G является 2-раскрашиваемой тогда и только тогда, когда G представляет собой гамильтонов граф

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

(4) карта G является 2-раскрашиваемой тогда и только тогда, когда G представляет собой орграф

Номер 2

Что называют жордановой кривой?

Ответ:

(1) жордановой кривой на плоскости называется непрерывная кривая, не имеющая самопересечений

(2) жордановой кривой называют жорданову дугу

(3) жордановой кривой называют замкнутую кривую на плоскости

(4) жордановой кривой называют самопересекающуюся кривую на плоскости

Номер 3

Что называется замкнутой жордановой кривой?

Ответ:

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

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

(3) замкнутой жордановой кривой называют самопересекающуюся жорданову дугу

(4) замкнутой жордановой кривой называют диаметр графа

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