Теоретическая часть (вопросы)

1. Что такое граф? Привести примеры.

2. Назовите известные вам типы графов.

3. В чем разница между ориентированным и неориентированным графом?

4. Опишите известные способы задания графов.

5. Какие ребра называются параллельными?

6. Когда ребро называется петлей?

7. Какой граф простой, пустой, нуль-граф?

8. Какая вершина называется висячей?

9. Что такое полный граф, пустой граф?

10. Что не допускается в мультиграфе, но допускается в псевдографе?

11. Когда два графа изоморфны?

12. Что такое инвариант графа?

13. Что такое подграф графа?

14. В каком случае подграф является правильным?

15. Что такое маршрут?

16. Как определить длину маршрута?

17. Что такое цепь, цикл, простой цикл, простая цепь?

18. Какие вы знаете свойства путей и циклов?

19. Какой граф называется связным?

20. Какие операции определены на графах? Привести их определения.

21. В чем отличие матрицы смежности от матрицы инцидентности?

22. Дайте определение орграфа. Что такое основание орграфа?

23. Что такое ориентированная цепь, ориентированный цикл, маршрут?

24. Какие вершины называются смежными?

25. В чем различие между связанным и сильно связанным орграфами?

26. Приведите пример матрицы смежности для орграфа.

27. Какие графы называют изоморфными?

28. Когда граф связен?

29. Какие виды матриц есть у орграфа?

30. Дайте определение эйлерового орграфа.

31. Дайте определение ориентированной эйлеровой цепи.

32. Что называется топологической сортировкой графа?

33. Что называется деревом? Перечислите известные Вам простые свойства деревьев.

34. Какой ориентированный граф можно назвать ациклическим?

35. Если G — лес с a вершинами и b компонентами, то сколько ребер имеет G?

36. Из некоторого графа с циклами удалили ребра, принадлежащие циклам, в результате чего получился граф без циклов. Как называется полученный граф?

37. Что называется цикломатическим числом графа?

38. Как получить фундаментальную систему циклов, ассоциированную с данным остовным деревом T?

39. Что такое планарный граф? Чем планарный граф отличается от плоского?

40. Как называется связанный с каждым полиэдром граф, состоящий из его точек и линий?

41. Какие два непланарных графа называются основными? Изобразите их.

42. Что общего между точкой сочленения и мостом?

43. Как построить граф, геометрически двойственный данному плоскому графу?

44. Если G* cn* вершинами, m* ребрами и f* гранями двойственен Gcn вершинами, m ребрами и f гранями, то какие имеют место соотношения?

45. Что означает абстрактная двойственность?

46. Если граф G* абстрактно двойствен к графу G, то что можно сказать об абстрактной двойственности Gк G*?

47. Как связана планарность и абстрактная двойственность?

48. Расскажите о стратегии исследования лабиринта, которая называется «исследованием Тремо».

49. Каким свойством обладает исследование Тремо?

50. Какие ситуации могут возникать при исследовании лабиринта методом «исследования Тремо»?

51. Поясните суть алгоритма поиска в глубину (DFS).

52. Поясните суть алгоритма поиска в ширину (BFS).

53. Какие задачи позволяет решать алгоритм поиска в ширину?

54. Приведите алгоритм Дейкстры нахождения минимального пути в графе.