Контрольные задания > А.3. На рисунке изображён граф. а) Найдите в этом графе кратчайший путь¹ из вершины А в вершину В. Чему равна длина² этого пути? б) Сколько кратчайших путей ведёт из вершины С в вершину В? в) Является ли связным граф³? г) Какова наименьшая длина цикла в этом графе? д) Какова наибольшая длина цикла в этом графе? А.4. На рисунках изображены графы. а) Укажите какие из графов, изображённых на рисунке (а), являются циклами. б) Укажите какие из графов, изображённых на рисунке (б), являются циклами. в) Укажите какие графы, изображённые на рисунке (а), не являются циклами, но содержат цикл. г) Укажите какие графы, изображённые на рисунке (б), не являются циклами, но содержат цикл.
Вопрос:

А.3. На рисунке изображён граф. а) Найдите в этом графе кратчайший путь¹ из вершины А в вершину В. Чему равна длина² этого пути? б) Сколько кратчайших путей ведёт из вершины С в вершину В? в) Является ли связным граф³? г) Какова наименьшая длина цикла в этом графе? д) Какова наибольшая длина цикла в этом графе? А.4. На рисунках изображены графы. а) Укажите какие из графов, изображённых на рисунке (а), являются циклами. б) Укажите какие из графов, изображённых на рисунке (б), являются циклами. в) Укажите какие графы, изображённые на рисунке (а), не являются циклами, но содержат цикл. г) Укажите какие графы, изображённые на рисунке (б), не являются циклами, но содержат цикл.

Ответ:

  • А.3
  1. а) Кратчайший путь из вершины А в вершину В: A -> F -> B. Длина этого пути равна 2.
  2. б) Из вершины С в вершину В ведёт 1 кратчайший путь: C -> D -> E -> B.
  3. в) Да, граф является связным.
  4. г) Наименьшая длина цикла в этом графе равна 3.
  5. д) Наибольшая длина цикла в этом графе равна 6 (C -> D -> E -> B -> F -> A -> C).
  • А.4
  1. а) Циклами являются графы 2 и 3.
  2. б) Циклом является граф 1.
  3. в) Графом, не являющимся циклом, но содержащим цикл, является граф 4.
  4. г) Графом, не являющимся циклом, но содержащим цикл, является граф 4.
Смотреть решения всех заданий с листа