Содержание
- 2. Маршруты Пусть G =(V, E) – н-граф. Маршрутом в графе G называется чередующаяся последовательность вершин и
- 3. Маршруты Вершина - начальная вершина маршрута М, - конечная, - внутренняя вершина, маршрут соединяющий и .
- 4. Маршруты Маршрут М называется цепью - если его ребра не повторяются, простой цепью – если его
- 5. Маршруты Маршрут М называется циклическим, если начальная и конечная вершина совпадают. Замечание: совпадают, не значит повторяются.
- 6. Маршруты Циклический маршрут М называется циклом - если его ребра не повторяются, простым циклом – если
- 7. Маршруты М1 =(1, 2, 3, 4, 1, 3, 4, 5) – общ вида. М1 =(1, 2,
- 8. Маршруты М1 =(1, 2, 3, 1, 2, 3, 1) – циклический маршрут общего вида. М1 =(1,
- 9. Расстояния в графе Расстоянием между вершинами a и b называется длина минимальной простой цепи, связывающей их.
- 10. Расстояния в графе
- 11. Расстояния в графе ri – эксцентриситет i-ой вершины – расстояние от этой вершины до наиболее удаленной
- 12. Расстояния в графе Диаметр графа G – максимальное расстояние между вершинами графа d(G)= max d(vi,vj) по
- 13. Расстояния в графе Центр графа G – это вершина, расстояние от которой до наиболее удаленной вершины
- 14. Расстояния в графе Радиус графа G –расстояние от центра графа до наиболее удаленной вершины. r(G)=min ri
- 15. Расстояния в графе Центр графа G –такая вершина i, для которой ri =r(G). Замечание: Центр в
- 16. Расстояния в графе В нашем примере центром является вершина 5. Радиус -1, диаметр – 2.
- 17. Расстояния в графе Диаметральные цепи графа G – простые цепи, длина которых равна d(G), соединяющие наиболее
- 18. Расстояния в графе Радиальные цепи графа G – простые цепи, длина которых равна r(G), соединяющие центр
- 20. Скачать презентацию