Домашнее задание №2 КРАТЧАЙШИЕ МАРШРУТЫ Вариант 20 (Теория конечных графов и ее применение. Сост. Додонова)

Цель работы – закрепление основных понятий теории графов. Задачи: усвоить понятия маршрута, цепи, цикла, радиуса графа, диаметра графа; усвоить работу алгоритмов определения кратчайших маршрутов в графах, отработать навыки работы с волновым алгоритмом, алгоритмами Дейкстры и Беллмана-Мура; использовать в расчетах программные средства. Задание 1. 1) В графе указать: маршрут, но не цепь; цепь, но не простую; простую цепь; цикл, но не простой; простой цикл. 2) Определить диаметральную цепь, длину диаметра; радиус; центр графа; периферийные вершины. 3) Выбрать правильный подграф F, содержащий вершины 1-9. В графе F найти число всех маршрутов длины 3. 4) Ориентировать граф F произвольным образом, найти число всех маршрутов длины 4. 5) С помощью волнового алгоритма в исходном графе определить кратчайшие расстояния (по количеству ребер) от вершин u и v, до остальных вершин графа.