Тест: Связность графов. Эйлеровы и гамильтоновы графы
Список вопросов
|
1. Дан граф с вершинами 1, 2, 3, 4, 5 и ребрами с концами 1 и 2, 1 и 4, 1 и 5, 4 и 5, 2 и 4, 2 и 3, 3 и 4. Существует ли на графе эйлерова цепь? |
|
| 1) нет | |
| 2) да | |
|
2. Дерево имеет бинарный код 0010101011. Сколько ребер этого графа являются перешейками? |
|
| 1) 1 | |
| 2) 3 | |
|
3. Граф представляет собой незамкнутую простую цепь с 24 вершинами. Сколько ребер этого графа являются перешейками? |
|
| 1) 45 | |
| 2) 24 | |
| 3) 21 | |
|
4. Дерево имеет код Прюффера 27277. Сколько ребер этого графа являются перешейками? |
|
| 1) 3 | |
| 2) 2 | |
| 3) 1 | |
|
5. Покажите графы, множество ребер которых можно разбить на циклы. (1)Граф, полученный путем удаления из полного графа с шестью вершинами двух смежных ребер. (2)Граф, полученный путем удаления из полного графа с пятью вершинами ребер цикла длины 3. (3)Полный граф с 28 ребрами. Ответ запишите в формате последовательности 0 и 1 без скобок, пробелов и запятых (например, 001): на первом меcте запишите 1, если для графа (1) разбиение возможно, в противном случае запишите 0; на втором месте запишите 1, если для графа (2) разбиение возможно, в противном случае запишите 0; и т.д. |
|
| 1) 010 | |
| 2) 123 | |
| 3) 001 | |
|
6. Графом называется… |
|
| 1) пара двух конечных множеств: множество точек и множество линий, соединяющих некоторые пары точек; | |
| 2) множество линий, соединяющих некоторые пары точек; | |
| 3) пара двух бесконечных множеств: множество точек и множество линий, соединяющих некоторые пары точек; | |
|
7. Ребра называются смежными, если они... |
|
| 1) параллельны; | |
| 2) являются кратными. | |
| 3) инцидентны одной и той же вершине; | |
|
8. Эйлеров цикл… |
|
| 1) проходит через все вершины и ребра графа только один раз. | |
| 2) содержит каждое ребро только один раз; | |
| 3) содержит каждую вершину только один раз; | |
|
9. В полуэйлеровом графе допускаются |
|
| 1) 2 вершины нечетной степени; | |
| 2) 1 вершина нечетной степени. | |
| 3) 3 вершины нечетной степени; | |
|
10. Граф содержит 7 дуг. Его эйлеров цикл будет состоять из: |
|
| 1) 8 дуг . | |
| 2) 7 дуг ; | |
| 3) 6 дуг; | |