№5 На рисунке изображен граф. а) Чему равна наименьшая из степеней его вершин? б) Запишите все пути от А до К

Анализ графа:

Рассмотрим данный граф.

• а) Наименьшая степень вершин:
  • Степень вершины А = 3 (ребра к Б, Г, Д).
  • Степень вершины Б = 3 (ребра к А, В, Ж).
  • Степень вершины В = 2 (ребра к Б, Ж, К).
  • Степень вершины Ж = 3 (ребра к Б, В, К).
  • Степень вершины К = 3 (ребра к Ж, И, Е).
  • Степень вершины И = 2 (ребра к К, Д).
  • Степень вершины Д = 2 (ребра к А, И, Г).
  • Степень вершины Г = 2 (ребра к А, Д, Е).
  • Степень вершины Е = 2 (ребра к Ж, Г, К).
  Наименьшая степень среди всех вершин равна 2.
• б) Пути от А до К: Путь – это последовательность вершин, где каждая следующая вершина соединена ребром с предыдущей.

Вот все возмомые пути от А до К:

• А-Б-Ж-К
• А-Г-Е-К
• А-Г-Д-И-К
• А-Д-И-К
• А-Д-Г-Е-К
• А-Б-В-Ж-К

Ответ: а) Наименьшая степень вершин равна 2. б) Пути от А до К: А-Б-Ж-К, А-Г-Е-К, А-Г-Д-И-К, А-Д-И-К, А-Д-Г-Е-К, А-Б-В-Ж-К.