Ученики на Учителя.com


Тест "Основы теории графов"

Тест: Основы теории графов
Задание №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)
этажом.
Скачать материал

Педагогика - еще материалы к урокам: