Пути, маршруты, цепи и циклы.
Основные понятия теории графов.
Граф это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Вершины, прилегающие к одному и тому же ребру, называются смежными. Если ребра ориентированы, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом. Если ребра не имеют ориентации, граф называется неориентированным.
Граф
Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими точки (рис. 1).Петля это дуга, начальная и конечная вершина которой совпадают.
Простой граф граф без кратных ребер и петель.
Степень вершины это удвоенное количество петель, находящихся у этой вершины плюс количество остальных Рис. 1 прилегающих к ней ребер.
Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные.
Пути, маршруты, цепи и циклы.
Путь в ориентированном графе — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей. Вершины v0, vn называются связанными данным путем (или просто связанными). Вершину v0 называют началом, vn - концом пути. Если v0 = vn, то путь называют замкнутым. Число n называется длиной пути.
Маршрут в графе путь, ориентацией дуг которого можно пренебречь. Цепь маршрут, в котором все ребра попарно различны. Цикл замкнутый маршрут, являющийся цепью.
Маршрут, в котором все вершины попарно различны, называют простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называются простым циклом.
Дата добавления: 2015-09-27 | Просмотры: 472 | Нарушение авторских прав
|