Определения. Неориентированный граф с шестью вершинами и семью рёбрами
Граф
Неориентированный граф с шестью вершинами и семью рёбрами
Граф, или неориентированный граф — это упорядоченная пара , для которой выполнены следующие условия:
· — это непустое множество вершин или узлов,
· — это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.
(а значит и, , иначе оно было бы мультимножеством) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становится ложным в случае бесконечных множеств.
Вершины и рёбра графа называются также элементами графа, число вершин в графе — порядком, число рёбер — размером графа.
Вершины и называются концевыми вершинами (или просто концами) ребра . Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.
Два ребра называются смежными, если они имеют общую концевую вершину.
Два ребра называются кратными, если множества их концевых вершин совпадают.
Ребро называется петлёй, если его концы совпадают, то есть .
Степенью вершины называют количество инцидентных ей рёбер (при этом петли считают дважды).
Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.
Дата добавления: 2015-09-27 | Просмотры: 600 | Нарушение авторских прав
|