Вопросы и задачи

  • 1. Дайте определение графа.
  • 2. Приведите примеры ориентированного, неориентированного и смешанного графов, которые состоят из пяти вершин и пяти ребер.
  • 3. Укажите на приведенных примерах смежные вершины, смежные ребра (дуги).
  • 4. Что означают термины «инцидентная дуга», «инцидентная вершина»?
  • 5. Дайте определение степени вершины, полустепени ее исхода и захода.
  • 6. Приведите пример графа с вершиной, имеющей степень 3, с полустепенью захода и полустепенью исхода, равными 2.
  • 7. Какие вершины графа называются изолированными?
  • 8. Какой граф называется полным? Неполным? Приведите примеры таких графов.
  • 9. Сколько ребер в полном графе с п вершинами?
  • 10. Дайте определение подграфа, остовного подграфа. Приведите примеры таких подграфов.
  • 11. Какой граф называется двудольным? Нарисуйте двудольный граф.
  • 12. Какой граф называется взвешенным? Приведите пример взвешенного графа с четырьмя ребрами и стоком.
  • 13. Дайте определение маршрута на графе. Как представляются маршруты?
  • 14. Приведите пример графа с шестью вершинами, семью ребрами и перечислите все маршруты этого графа.
  • 15. Какой маршрут называется цепью? Покажите на рисунке любого графа цепи и маршруты.
  • 16. Какой маршрут называется циклическим? Приведите пример графа, содержащего цикл.
  • 17. Какой граф называется ациклическим?

а Ь

•-И

С (1

18. Дан орграф •-*». Постройте все орграфы, связывая

вершины (а, сГ) и вершины (с, Ь) ребрами различной ориентации.

Сколько будет таких графов? Имеется ли среди них граф с циклом?

  • 19. Что значит термин «длина дуги» для взвешенного орграфа? Приведите пример взвешенного орграфа, укажите на нем любой путь и определите его длину.
  • 20. Какие вершины графа называются связными?
  • 21. Что означает термин «достижимая» вершина?
  • 22. Какой граф называется связным? Несвязным? Приведите пример связного графа с пятью вершинами и пятью ребрами. Преобразуйте этот граф в несвязный.
  • 23. Дайте определение дерева, леса, корневого дерева.
  • 24. Приведите пример корневого бинарного дерева высотой 2.

Сколько листьев содержит такое дерево? Сколько в нем вершин?

  • 25. Приведите пример корневого тернарного дерева высотой 2. Сколько в нем вершин?
  • 26. Какие графы называются изоморфными? Как установить изоморфность графов?
  • 27. Приведите пример изоморфных графов.
  • 28. Какие графы называются плоскими? Приведите пример плоского графа.
  • 29. Какие графы называются экстремальными?
  • 30. Перечислите известные вам формы представления графов. Какая форма самая удобная для определения характеристик графа?
  • 31. Приведите пример представления графа при помощи матрицы смежностей.
  • 32. Как представляется граф при помощи матрицы инциден-ций? Приведите пример представления графа этим способом.
  • 33. Как представляется граф при помощи векторов смежностей? Приведите пример представления графа этим способом.
  • 34. Есть ли наилучший способ представления графа?
Матрицы смежности графов, приведенных на рис. 2.18

Рис. 2.20. Матрицы смежности графов, приведенных на рис. 2.18: а — орграфа; б — неориентированного графа

 
< Пред   СОДЕРЖАНИЕ     След >