Тест: Операции над графами. Изоморфизм графов. Плоские и планарные графы
Список вопросов
|
1. Графом называется… |
|
| 1) множество линий, соединяющих некоторые пары точек; | |
| 2) пара двух бесконечных множеств: множество точек и множество линий, соединяющих некоторые пары точек; | |
| 3) пара двух конечных множеств: множество точек и множество линий, соединяющих некоторые пары точек; | |
|
2. Ребра называются смежными, если они... |
|
| 1) являются кратными. | |
| 2) параллельны; | |
| 3) инцидентны одной и той же вершине; | |
|
3. Эйлеров цикл… |
|
| 1) проходит через все вершины и ребра графа только один раз. | |
| 2) содержит каждую вершину только один раз; | |
| 3) содержит каждое ребро только один раз; | |
|
4. Гамильтонов цикл… |
|
| 1) содержит каждую вершину только один раз; | |
| 2) проходит через все вершины и ребра графа только один раз. | |
| 3) содержит каждое ребро только один раз; | |
|
5. В эйлеровом графе все вершины |
|
| 1) нечетной степени. | |
| 2) четной степени; | |
|
6. В полуэйлеровом графе допускаются |
|
| 1) 1 вершина нечетной степени. | |
| 2) 2 вершины нечетной степени; | |
| 3) 3 вершины нечетной степени; | |
|
7. Какой из циклов графа с множеством вершин {a,b,c,d,e,f} является гамильтоновым? |
|
| 1) fbecdf | |
| 2) abecdfa | |
| 3) abeca | |
|
8. Граф содержит 7 дуг. Его эйлеров цикл будет состоять из: |
|
| 1) 5 дуг; | |
| 2) 7 дуг; | |
| 3) 6 дуг; | |
|
9. Простая цепь это: |
|
| 1) маршрут, где нет повторяющихся вершин; | |
| 2) маршрут, где нет повторяющихся ребер; | |
| 3) маршрут, где нет повторяющихся вершин и ребер. | |
|
10. Расстояние между вершинами есть... |
|
| 1) сумма длин ребер, входящих в путь; | |
| 2) длина кратчайшего пути. | |