Пути, контуры в ориентированном графе
Следует усвоить, что понятиям ребра, маршрз’та, цепи, цикла в неориентированном графе соответствуют понятия дуги, пути, ориентированной цепи, контура в ориентированном графе. Для лучшего запоминания приведем эти термины в таблице (табл. 3.6). Путем ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной… Читать ещё >
Пути, контуры в ориентированном графе (реферат, курсовая, диплом, контрольная)
Понятия пути, контура в ориентированном графе аналогичны понятиям маршрута, цикла в неориентированном графе.
Путем ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей дуги.
Число дуг пути называется длиной пути.
Путь называется контуром, если его начальная вершина совпадает с конечной.
Путь (контур), в котором все душ различны, называется простым.
Путь (контур), в котором все вершины, кроме первой и последней, различны, называется элементарным.
Следует усвоить, что понятиям ребра, маршрз’та, цепи, цикла в неориентированном графе соответствуют понятия дуги, пути, ориентированной цепи, контура в ориентированном графе. Для лучшего запоминания приведем эти термины в таблице (табл. 3.6).
Соответствие понятий в ориентированном и неориентированном графах.
Неориентированный граф. | Ориентированный граф. |
Ребро. | Дуга. |
Маршрут. | Путь. |
Цикл. | Контур |
Пример 3.9. В приведенном на рис. 3.27 графе выделим следующие пути:
- • (х, х2, х3, х4) — простой элементарный путь, гак как каждая вершина и каждая дуга используются не более одного раза;
- • (х2, х5, х6, х7, х2) — простой элементарный контур, так как это замкнутый путь, в котором все дуги и вершины, кроме первой и последней, различны.
Рис. 3.27. Граф (пример 3.9)