Тест "Графы"
тест по теме

Тест

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

Вариант 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: (а-в)  с помощью ориентированного упорядоченного дерева.