Практическая работа №12. Маршруты связных графов, оценка по их цене (расстоянию)

Окружение графа G – длина наибольшего простого цикла графа G (если он существует).
Расстояние d(u,v) между двумя несовпадающими вершинами u и v – длина кратчайшей простой цепи, соединяющей эти вершины.
Геодезическая (u,v) – кратчайшая простая цепь между вершинами u и v, доставляющая расстояние между этими вершинами.


Матрица расстояний
Матрица расстояний D(G) – квадратная матрица p*p, где p – количество вершин графа G: ,

Эксцентриситет e(v) вершины v графа G – длина максимальной геодезической, исходящей из вершины v:
.
Диаметр D(G) графа G – максимальный среди всех эксцентриситетов вершин графа G:
.
Радиус R(G) графа G – минимальный среди всех эксцентриситетов вершин графа G:
.
Периферия графа G – множество вершин графа G, у которых эксцентриситет равен диаметру.
Центр графа G – множество всех вершин графа G, у которых эксцентриситет равен радиусу.
Например:
Граф G: вес каждого ребра равен 1.

Матрица расстояний D_G

j i	1	2	3	4	5	6	e(j)
1	0	1	2	1	1	2	2
2	1	0	1	2	2	1	2
3	2	1	0	1	2	1	2
4	1	2	1	0	1	1	2
5	1	2	2	1	0	1	2
6	2	1	1	1	1	0	2

Диаметр G: D(G)=2. Радиус G: R(G)=2.

Периферия графа G={1,2,3,4,5,6}.
Центр графа G = {1,2,3,4,5,6}.
Обхват графа G = 3.
Окружение графа G = 6, максимальный простой цикл, который содержит все вершины графа G (1,2,3,4,6,5,1).


3. Задание на Практическую работу

Ориентированный граф G=(V,E,O) задан аналитическим способом.

Необходимо:

1. 
   задать граф геометрическим способом;
   
2. 
   определить полустепени вершин графа;
   
3. 
   определить матрицу смежности
   
4. 
   определить матрицу инцидентности
   

Для проверки решения использовать программу Grin

Варианты:

1. 
   V = (v₁,v₂,v₃,v₄,v₅), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉,e₁₀), O = ((v₁,v₁), (v₁,v₃), (v₁,v₅), (v₂,v₃), (v₂,v₄), (v₂,v₅), (v₃,v₃), (v₃,v₄), (v₄,v₅), (v₅,v₅)).
   
2. 
   V = (v₁,v₂,v₃,v₄,v₅), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉,e₁₀,e₁₁), O = ((v₁,v₂), (v₁,v₃), (v₁,v₄), (v₁,v₅), (v₂,v₂), (v₂,v₃), (v₂,v₅), (v₃,v₃), (v₃,v₄), (v₄,v₄), (v₄,v₅)).
   
3. 
   V = (v₁,v₂,v₃,v₄,v₅), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉,e₁₀), O = ((v₁,v₂), (v₁,v₄), (v₁,v₅), (v₂,v₂), (v₂,v₃), (v₂,v₅), (v₃,v₄), (v₃,v₅), (v₄,v₄), (v₅,v₅)).
   
4. 
   V = (v₁,v₂,v₃,v₄,v₅), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉,e₁₀), O = ((v₁,v₂), (v₁,v₃), (v₂,v₂), (v₂,v₄), (v₂,v₅), (v₃,v₄), (v₃,v₅), (v₄,v₄), (v₄,v₅), (v₅,v₅)).
   
5. 
   V = (v₁,v₂,v₃,v₄,v₅), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉,e₁₀,e₁₁), O = ((v₁,v₁), (v₁,v₃), (v₁,v₄), (v₁,v₅), (v₂,v₂), (v₂,v₄), (v₂,v₅), (v₃,v₃), (v₃,v₅), (v₄,v₄), (v₄,v₅)).
   
6. 
   V = (v₁,v₂,v₃,v₄,v₅), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉,e₁₀), O = ((v₁,v₃), (v₁,v₄), (v₁,v₅), (v₂,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₃), (v₃,v₅), (v₄,v₄), (v₅,v₅)).
   
7. 
   V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈), O = ((v₁,v₁), (v₁,v₃), (v₁,v₂), (v₂,v₂), (v₂,v₄), (v₃,v₂), (v₃,v₃), (v₃,v₄)).
   
8. 
   V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆, e₇,e₈ ), O = ((v₁,v₁), (v₁,v₂), (v₁,v₃), (v₁,v₄), (v₂,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₃)).
   
9. 
   V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈), O = ((v₁,v₂), (v₁,v₃), (v₁,v₄), (v₂,v₂), (v₂,v₄), (v₃,v₂), (v₃,v₃), (v₄,v₃)).
   
10. 
    V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇), O = ((v₁,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₃), (v₄,v₁), (v₄,v₄), (v₃,v₄)).
    
11. 
    V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉), O = ((v₁,v₁), (v₁,v₂), (v₂,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₁), (v₃,v₃), (v₃,v₄), (v₄,v₁))
    
12. 
    V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉), O = ((v₁,v₁), (v₁,v₂), (v₂,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₁), (v₃,v₃), (v₃,v₄), (v₄,v₁)).
    
13. 
    V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈), O = ((v₁,v₁), (v₁,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₁), (v₃,v₃), (v₃,v₄), (v₄,v₁)).
    
14. 
    V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉), O = ((v₁,v₁), (v₁,v₃), (v₁,v₂), (v₂,v₂), (v₂,v₄), (v₃,v₂), (v₃,v₃), (v₃,v₄), (v₄,v₃)).
    
15. 
    V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈), O = ((v₁,v₁), (v₁,v₂), (v₁,v₃), (v₁,v₄), (v₂,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₃)).
    
16. 
    V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆, e₇,e₈ ), O = ((v₁,v₁), (v₁,v₂), (v₁,v₃), (v₁,v₄), (v₂,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₃)).
    
17. 
    V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈), O = ((v₁,v₂), (v₁,v₃), (v₁,v₄), (v₂,v₂), (v₂,v₄), (v₃,v₂), (v₃,v₃), (v₄,v₃)).
    
18. 
    V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇), O = ((v₁,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₃), (v₄,v₁), (v₄,v₄), (v₃,v₄)).
    
19. 
    V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉), O = ((v₁,v₁), (v₁,v₂), (v₂,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₁), (v₃,v₃), (v₃,v₄), (v₄,v₁))
    
20. 
    V = (v₁,v₂,v₃,v₄), E= (e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈,e₉), O = ((v₁,v₁), (v₁,v₂), (v₂,v₂), (v₂,v₃), (v₂,v₄), (v₃,v₁), (v₃,v₃), (v₃,v₄), (v₄,v₁)).
    

4. Содержание отчета
В отчете следует указать:

• 
  Название работы.
  
• 
  Цель работы.
  
• 
  Теоретическая часть.
  
• 
  Выполненное задание.
  
• 
  Заключение (выводы).
  
• 
  Литература.
  

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

1. 
   Понятие графа; ориентированные и неориентированные графы; способы задания графов.
   
2. 
   Часть графа, суграф, покрывающий суграф, подграф на заданных вершинах, звездный граф.
   
3. 
   Операции с частями графа (дополнение, объединение, пересечение).
   
4. 
   Циклы, маршруты, цепи, простые цепи в графах.
   
5. 
   Связность, степени вершин графа, эйлеров цикл, эйлерова цепь в графах.
   
6. 
   Остовное дерево графа. Построение остовного дерева с минимальным весом.
   
7. 
   Расстояние между вершинами графа; диаметр, радиус и центр графа.
   
8. 
   Протяженность между вершинами графа; диаметр протяженности, радиус протяженности и центр протяженности графа.
   
9. 
   Привести пример графа, удовлетворяющего строгому неравенству теоремы Уитни.
   
10. 
    Привести примеры графов, которые имеют все периферийные и все центральные вершины.
    
11. 
    Что такое эксцентриситет?
    
12. 
    Чем диаметр графа отличается от его радиуса (дайте их определения)?
    
13. 
    Чем простая цепь отличается от цикла?
    
14. 
    Что такое маршрут?
    
15. 
    Что такое число рёберной связности?
    
16. 
    Дайте определения моста и цикла.