Задание к лабораторной работе

Исходные данные: граф G1: GV(13,{6,7})

граф G2: GV(7,{2,3}).

Ребра графа G2 взвешены соответствующими элементами матрицы Y.

Алгоритм генерации вариантаGV(p,X)описан в приложении А.

1. Определить, является ли граф G1 связным.

2. Для максимальной компоненты графа G1:

a) выделить маршрут не цепь, замкнутый маршрут не цепь, цепь, простую цепь, цикл, простой цикл;

б) определить обхват и окружение;

в) найти вершинную и реберную связность.

3. Для каждой компоненты графа G1:

а) построить матрицу расстояний, определить эксцентриситеты вершин, радиус, диаметр, центр, периферию, диаметральную цепь;

б) определить, является ли она неразделимой, выделить блоки, найти точки сочленения и мосты.

4. В графе G2

а) построить кратчайшие маршруты от произвольной вершины ко всем остальным при помощи алгоритма Дейкстры;

б) построить кратчайшие маршруты от произвольной вершины ко всем остальным при помощи алгоритма Форда;

в) построить кратчайшие маршруты при помощи алгоритма Флойда. При построении вести две матрицы – матрицу маршрутов и матрицу расстояний.

Контрольные вопросы

1. Привести пример графа, удовлетворяющего строгому неравенству теоремы Уитни.

2. Привести примеры графов, которые имеют все периферийные и все центральные вершины.

3. Что такое эксцентриситет?

4. Чем диаметр графа отличается от его радиуса (дайте их определения)?

5. Чем простая цепь отличается от цикла?

6. Что такое маршрут?

7. Что такое число рёберной связности?

8. Дайте определения моста и цикла.

Лабораторная работа №3