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

Задание №1

Графом называется…

1)

пара двух конечных множеств: множество точек и множество линий, соединяющих некоторые пары точек;

2)

пара двух бесконечных множеств: множество точек и множество линий, соединяющих некоторые пары точек;

3)

множество линий, соединяющих некоторые пары точек;

4)

пара двух конечных множеств: множество точек и множество линий.

Задание №2

Точки графа называются…

1)

Ответ:

Задание №3

Линии графа называются…

1)

Ответ:

Задание №4

Если ребро графа  соединяет две его вершины, то говорят, что это ребро им…

1)

Ответ:

Задание №5

Если существует ребро, инцидентное двум вершинам графа, то эти вершины являются…

1)

Ответ:

Задание №6

Ребро, имеющее совпадающие начало и конец, называется…

1)

Ответ:

Задание №7

Эйлеров цикл…

1)

содержит каждое ребро только один раз;

2)

содержит каждую вершину только один раз;

3)

проходит через все вершины и ребра графа только один раз.

Задание №8

Гамильтонов цикл…

1)

содержит каждое ребро только один раз;

2)

содержит каждую вершину только один раз;

3)

проходит через все вершины и ребра графа только один раз.

Задание №9

В полуэйлеровом графе допускаются

1)

3 вершины нечетной степени;

2)

2 вершины нечетной степени;

3)

1 вершина нечетной степени.

Задание №10

Простая цепь это:

1)

маршрут минимальной стоимости;

2)

маршрут, где нет повторяющихся вершин;

3)

маршрут, где нет повторяющихся ребер;

4)

маршрут, где нет повторяющихся вершин и ребер.

Задание №11

Расстояние между вершинами есть...

1)

сумма длин ребер, входящих в путь;

2)

длина кратчайшего пути.

Задание №12

Дерево есть...

1)

связный граф;

2)

граф без циклов;

3)

остовный подграф графа;

4)

связный граф без циклов.

Задание №13

Если любые две вершины графа можно соединить простой цепью, то граф называется:

1)

связным;

2)

несвязным;

3)

деревом;

4)

остовом.

Задание №14

Ребра называются кратными, если они...

1)

инцидентны одной и той же вершине;

2)

параллельны;

3)

являются смежными;

4)

имеют одинаковые направления.

Задание №15

Расстояние до вершины дерева называют:

1)

ярусом вершины;

2)

высотой вершины;

3)

удаленностью вершины;

4)

этажом.