Читайте также:
|
Граф G = (V, E) -непустое множество вершин V и ребер E (являющееся подмножеством V 2), их соединяющих. Граф можно визуально представить в виде точек вершин, а также направленных отрезков, соединяющие их ребра.
Граф называется взвешенным, если каждому ребру поставлено в соответствие некоторое число, называемое весом ребра. Циклом называют путь, в котором первая и
последняя вершины совпадают.
Связный граф такой граф, между любой парой вершин которого, существует по крайней мере один путь. Дерево это связный ацикличный граф. Ацикличность означает, что между любой парой вершин в дереве существует только один путь. Остовное дерево связного неориентированного графа поддерево данного графа, в который входят все его вершины. Неформально говоря, остовное дерево состоит из некоторого подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим ребрам, и в нём нет циклов, то есть из любой вершины нельзя попасть в саму себя, не пройдя какое-то ребро дважды.
Минимальное остовное дерево в связанном, взвешенном, неориентированном графе это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
Дата добавления: 2015-08-18; просмотров: 55 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Введение | | | Алгоритм Краскала |