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

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

Номер 1

Какие орграфы называются простыми?

Ответ:

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

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

(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₂ так, что каждое ребро в орграфе соединяет какую-нибудь вершину из V₁ с какой-либо вершиной из V₁

Номер 2

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

Ответ:

(1) орграф D связен, или слабо связен, если он не может быть представлен в виде объединения двух различных орграфов (определенных обычным образом)

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

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

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

Номер 3

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

Ответ:

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

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

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

(4) пусть D - сильно связный орграф, имеющий n вершин. Если и для любой его вершины v, то D является эйлеровым орграфом

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

Номер 1

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

Ответ:

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

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

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

Номер 2

Что называют источником орграфа D?

Ответ:

(1) вершину, у которой полустепень захода равна нулю

(2) называют вершину, у которой полустепень исхода равна нулю

(3) компоненты связного орграфа

(4) вершины с максимальной степенью

Номер 3

Что называют стоком орграфа?

Ответ:

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

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

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

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

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

Номер 1

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

Ответ:

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

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

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

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

Номер 2

Может ли быть турнир полугамильтонов?

Ответ:

(1) всякий турнир полугамильтонов

(2) турниры не могут быть полугамильтоновыми

(3) если турнир имеет меньше четырех вершин, то утверждение, очевидно, верно

(4) если турнир является мостом

Номер 3

Может ли быть сильно связный турнир гамильтонов?

Ответ:

(1) всякий сильно связный турнир гамильтонов

(2) да, если сильно связный турнир T с n вершинами содержит орциклы длины 3,4,...,n

(3) всякий сильно связный турнир не может быть гамильтоновым

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

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