Итоговый тест по теме «Основы теории графов»

 

1. Как называют граф, если множества его вершин и ребер является конечным:

1) бесконечным;

2) эйлеровым;

3) конечным;

4) мультиграфом.

2. Количество вершин п(G) графа G – это:

1) четность графа;

2) смежность вершин;

3) порядок графа G;

4) кратность ребер графа G.

3. Количество ребер графа, инцидентных некоторой вершине v, называют:

1) степенью графа;

2) локальной степенью вершины;

3) множеством вершин графа;

4) смежными ребрами.

4. Если две вершины инцидентны одному ребру, то их называют:

1) смежными;

2) конечными вершинами этого ребра;

3) инцидентными друг другу;

4) несмежными.

5. Граф с непустым множеством вершин и пустым множеством ребер называют:

1) пустым;

2) непустым;

3) нуль-графом;

4) невидимым.

6. Как называют граф, у которого множества вершин и ребер пустые:

1) пустым;

2) непустым;

3) нуль-графом;

4) невидимым.

7. Как называют ребра, инцидентные одной и той же паре вершин:

1) смежными;

2) кратными;

3) петлей;

4) инцидентными друг другу.

8. Как называют ребро, соединяющее любую вершину саму с собой:

1) инцидентным само по себе;

2) гамильтоновым;

3) петлей;

4) смежным другом ребру.

9. Граф с петлями и кратными ребрами называют:

1) псевдографом;

2) мультиграфом;

3) нуль-графом;

4) обычным.

10. Как называют конечный неориентированный граф без петель и кратных ребер:

1) псевдографом;

2) обычным;

3) нуль-графом;

4) мультиграфом.

11. Если пары (v_i, v_j) считают упорядоченными, то граф называют:

1) псевдографом;

2) мультиграфом;

3) нуль-графом;

4) орграфом.

12. Ребра ориентированного графа называют:

1) дугами;

2) петлями.

13. Граф, имеющий как ребра, так и дуги, называют:

1) орграфом;

2) мультиграфом;

3) обычным;

4) смешанным.

14. Если множества вершин и ребер графа конечные, то граф является:

1) бесконечным;

2) взвешенным;

3) смешанным;

4) конечным.

15. Порядком графа называют:

1) количество вершин;

2) количество ребер;

3) множество ребер;

4) множество вершин.

16. Локальная степень вершины v графа G – это:

1) количество вершин в графе G;

2) количество ребер, инцидентных вершине v;

3) вес ребер, инцидентных вершине v;

4) кратность ребер, инцидентных вершине v.

17. Являются ли представленные графы изоморфными:

1) да;

2) нет?

18. Для приведенного графа определите локальные степени его вершин:

1) ρ(v₁) = 3, ρ(v₂) = 2, ρ(v₃) = 4,

ρ(v₄) = 3, ρ(v₅) = 2;

2) ρ(v1) = 2, ρ(v2) = 3,ρ(v3) = 5,

ρ(v4) = 3, ρ(v5) = 2;

3) ρ(v1) = 3, ρ(v2) = 5, ρ(v3) = 7,

ρ(v4) = 3, ρ(v5) = l;

4) ρ(v1) = 4, ρ(v2) = 5, ρ(v3) = 3,

ρ(v4) = 4, ρ(v5) = 5.

19. Конечный неориентированный граф без петель и ребер – это:

1) простой граф;

2) суграф;

3) взвешенный граф;

4) нуль-граф.

20. Каждая дуга ориентированного графа G имеет:

1) одно начало и два конца;

2) два начала и один конец;

3) одно начало и один конец;

4) все предыдущие ответы является неправильными.

21. Количество ребер маршрута называют его:

1) порядком;

2) плотностью;

3) длиной;

4) размерностью.

22. Маршрут М называют цепью, если каждое ребро встречается в нем:

1) не менее одного раза;

2) не более одного раза;

3) не более двух раз;

4) не менее двух раз.

23. Если первая вершина маршрута совпадает с последней, то маршрут называют:

1) незамкнутым;

2) простым;

3) сложным

4) замкнутым.

24. Если цепь является замкнутой, то ее называют:

1) простым деревом;

2) простым циклом;

3) деревом;

4) циклом.

25. Если каждая вершина встречается в маршруте не более чем один раз, то его называют:

1) простым циклом;

2) цепью;

3) циклом;

4) простой цепью.

26. Маршрут в ориентированном графе называют:

1) циклом;

2) обходом;

3) путем;

4) цепью.

27. Простой цикл в ориентированном графе еще называют:

1) рамкой;

2) обложкой;

3) кольцом;

4) контуром.

28. В обычном графе маршрут можно задавать последовательностью его:

1) вершин;

2) петель;

3) цепей;

4) циклов.