Please enable JavaScript.
Coggle requires JavaScript to display documents.
Графы story-py-graph-7599c3ea - Coggle Diagram
Графы
Маршрут в графе- это чередующаяся последовательность вершин и рёбер в которой любые два соседних элемента инцидентны.
Пример маршрута
Граф— множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется упорядоченная пара G=(V,E), где V — это непустое множество вершин или узлов, а E — это множество пар вершин, называемых рёбрами.
Путь в графе- последовательность вершин, в которой каждая вершина соединена со следующим ребром.
Пример пути
Простой путь- это последовательность дуг, в которой каждая следующая дуга имеет началом конец предыдущей и каждая дуга встречается не более одного раза
-
Цикл в графе- путь, в котором начальная и конечная вершины совпадают. Длиной цикла называется число ребер в этом цикле.
-
Длина пути- – количество дуг, входящих в этот путь. Длина пути (для нагруженного графа) – сумма весов дуг, входящих в этот путь.
Связный граф-граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует как минимум один путь.
-
-
Эйлеров граф- граф, содержащий эйлеров цикл.
-
-
Эйлеров путь- это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Эйлеров цикл- эйлеров путь, являющийся циклом, то есть замкнутый путь, проходящий через каждое ребро графа ровно по одному разу.