Тест Графы

Тест

Тема: Теория графов

Вариант 1

Часть 1

1.1. На рисунке изображен :

Изобразите с помощью графа договор

а) Полный граф; б) неполный граф; в) граф типа «дерево» г) нулевой;

1.2. Полный граф имеет 7 вершин, то количество ребер будет равно:

а) 14; б) 21; в) 7; г) 42.

1.3. Какие из указанных в графе на рисунке маршрутов являются путем?

Изобразите с помощью графа отношения между

а) АВГВД б) АВГ в) АВДАБ г) АБВАД

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

а) АВГА б) АБВГБА; в) ВБАГВ; г) ДВАГВД

1.5. Хроматическое число графа на рисунке равно:

Изобразите с помощью графа договор

а) 3; б) 6; в) 4; г) 2.

Часть 2

2.1. Сколько ребер нужно провести чтобы достроить граф, изображенный на рисунке до полного?

Изобразите с помощью графа договор

2.2. Назвать наибольшее число висячих вершин, дерева с 10-ю вершинами.

2.3. Укажите критерий эйлеровости графа.

Часть 3

3. 1. Изобразите с помощью графа договорные отношения между предприятиями А, Б, В, Г, Д, Е, если к рассматриваемому моменту: предприятие А установило договорные отношения со всеми другими предприятиями;Б установило с Г и Д; В установило со всеми предприятиями, кроме предприятия Е. Сколько вершин и сколько ребер имеет полученный граф?

3.2. Представьте выражение 14+с*а помощью ориентированного упорядоченного дерева.

Тест

Тема: Теория графов

Вариант 2

Часть 1

1.1. На рисунке изображен :

Изобразите с помощью графа отношения между

а) Полный граф; б) неполный граф; в) граф типа «дерево» г) нулевой;

1.2. Полный граф имеет 9 вершин, то количество ребер будет равно:

а) 18; б) 72; в) 9; г) 36.

1.3. Какие из указанных в графе на рисунке маршрутов являются путем?

Изобразите с помощью графа договор

а) АВГВБ б) АВГВ в) АВДАГ г) АБВ

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

а) АВГДВА б) АБВГВА; в) ВБАГВ; г) ДВАГВД

1.5. Хроматическое число графа на рисунке равно:

а) 3; б) 6; в) 4; г) 2.

Часть 2

2.1. Сколько ребер нужно провести, чтобы достроить граф, изображенный на рисунке, до полного?

Изобразите с помощью графа договор

2.2. Назвать наименьшее число висячих вершин, дерева с 15-ю вершинами

2.3. Сформулируйте достаточные условия гамильтоновости графа.

Часть 3

3.1. Среди семи стран установлены экономические отношения, причем каждая страна имеет экономические договоры с каждой другой страной. Изобразите в виде графа результат установленных экономических отношений. Сколько вершин и ребер имеет полученный граф?

3.2. Представьте выражение 25: (а-в) с помощью ориентированного упорядоченного дерева.