И код направления подготовки
жүктеу/скачать 341.63 Kb.
|
- Бұл бет үшін навигация:
- Определение.
- Поиск маршрутов в графе.
| Частичный граф – DC по отношению к графу D называется граф, содержащий все вершины рассматриваемого графа и только часть дуг этого графа.
Определение. Последовательность v1x1v2x2v3…xkvk+1, (где k1, viV, i=1,…,k+1, xiX, j=1,…,k), в которой для неориентированного графа чередуются вершины и ребра и для каждого j=1,…, k ребро xj имеет вид {vj,vj+1}, называется маршрутом, соединяющим вершины v1 и vk+1. Определение. Последовательность v1x1v2x2v3…xkvk+1, (где k1, viV, i=1,…,k+1, xiX, j=1,…,k), в которой для ориентированного графа чередуются вершины и дуги и для каждого j=1,…, k дуга xj имеет вид (vj,vj+1), называется путем из v1 в vk+1. Определение. Цепь − незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны. Определение. Цикл − замкнутая цепь (в неориентированном графе). Определение. Контур − замкнутый путь (в ориентированном графе). Определение. Простой путь (цепь) − путь (цепь, цикл, контур), в котором ни одна дуга/ребро не встречается дважды. Определение. Простой цикл (контур) − цикл (контур), в котором все вершины попарно различны. Определение. Длина маршрута (пути) − число ребер в маршруте (дуг в пути). Еще раз напомним, что подграфом графа G (ориентированного графа D) называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G (D). Подграф называется собственным, если он отличен от самого графа. Говорят, что вершина w ориентированного графа D (графа G) достижима из вершины v, если либо w=v, либо существует путь (маршрут) из v в w. Граф (ориентированный граф) называется связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v и w. Про неориентированные графы говорят еще, что они слабо связны. Вопросы для закрепления: Что называется подграфом? Частичным графом? Что называется цепью? Циклом? Контуром? Простым путем? Простым циклом? Что такое длина маршрута? Литература: Основная [1] стр.152- 154, [3]стр. 288-291; дополнительная [1],[2]; Интернет ресурсы [1]-[4] Тема 10 Поиск маршрутов в графе. Количество часов 1 Основные вопросы/план темы: Расстояния в графе. Задача о кратчайшем пути. Алгоритм поиска минимального пути в ориентированном графе. Тезисы лекции*: жүктеу/скачать 341.63 Kb. Достарыңызбен бөлісу:
|