Графы

Графом называется множество точек (вершин), некоторые из которых соединены отрезками (ребрами).

Граф является ориентированным, если для каждого ребра задано направление, в котором возможно движение по этому ребру. Если движение возможно в обоих направлениях, то граф называется неориентированным.

Неориентированный, несвязный, невзвешенный граф

Граф называется взвешенным, если каждому ребру поставлено в соответствие некоторое число (вес).

Граф называется связным, если из любой его вершины существует путь (не обязательно состоящий из одного ребра) в любую другую.

Часть графа, которая является связной, называется компонентой связности. В графе, изображенном на рисунке две компоненты связности.

Степенью вершины (в неориентированном графе) называется количество выходящих из нее ребер.

Полустепенью вершины (в ориентированном графе) называется количество выходящих из нее ребер (полустепень исхода) или количество входящих ребер (полустепень захода).

Истоком(в ориентированном графе) называется вершина, в которую не входит ни одно ребро.

Красным цветом показаны ребра, образующие цикл

Стоком (в ориентированном графе) называется вершина, из которой не выходит ни одного ребра.

Петлей называется ребро, соединяющее вершину с самой собой.

Простым путем в графе называется путь, в котором ни одно ребро не встречается дважды.

Циклом называется путь, не проходящий дважды через одну и ту же вершину.

Деревом называется граф, не содержащий циклов.


Оставить комментарий