Информационные модели. Графы

швейцарский, немецкий и российский математик) , в которых он описывал

решение головоломок и математических развлекательных задач.
Теория графов началась с решения Эйлером задачи о семи мостах Кёнигсберга.

по всем мостам (через реку Преголя), не проходя ни по

одному из них дважды? Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.

На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа).

В ходе рассуждений Эйлер пришёл к следующим выводам: Невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

к другому не все группы совместимы. Но известно, что одинаковые

группы можно переливать от человека к человеку, т.е.
1 – 1, 2 – 2 и т.д.
А также 1 группу можно переливать всем остальным группам,
2 и 3 группу только 4 группе.

Задача.

множество вершин (узлов), соединённых рёбрами.
Граф с шестью вершинами и семью

рёбрами.

Вершины называют смежными, если их соединяет ребро.

дугами.

Ориентированный граф

числовые величины (они могут обозначать, например, расстояние между городами или

стоимость перевозки).
Вес графа равен сумме весов его рёбер.

Таблице (она называется весовой матрицей) соответствует граф.

дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице

означает, что прямой дороги между пунктами нет). Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

1) 9 2) 10 3) 11 4) 12

строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними

станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.

В, Г, Д, Е, Ж, И, К. По каждой дороге можно

двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Графы. Поиск путей.