Информационные технологии проектирования электронных средств

- 17 - Путь, в котором каждая дуга повторяется не более одного раза, называет- ся простым. Элементарным называется путь, в котором каждая вершина повто- ряется не более одного раза. Длиной (мощностью) пути называется число дуг, входящих в него. При этом каждая дуга считается столько раз, сколько она входит в этот путь. Петлей называется дуга, начальная и конечная вершины которой совпадают. Путь е 1 , е 2 ,…, е k называется замкнутым, если в нем начальная вершина ду- ги е 1 совпадает с конечной вершиной дуги е k . Замкнутый маршрут является не- ориентированным двойником замкнутого пути. Вершина, из которой выходит дуга, называется исходящей. Вершина захода − такая вершина, в которую дуга входит. Число дуг, которые имеют вершину х j cвоей начальной вершиной, назы- вают полустепенью исхода вершины х j и обозначают d 0 ( x j ) . Число дуг, которые имеют вершину х k своей конечной вершиной, назы- вают полустепенью захода вершины x k и обозначают d t ( x k ) . Для всех вершин графа ( ) ( ) m xd xd n i i t i n i = ∑ = = ∑ = 1 1 0 , где m – общее число дуг. Для неориентированного графа G ( X,Е ) степень вершины определяется как d ( x i ) ≡ Г( x i )  . Двудольным графом называется граф, у которого множество вершин Х состоит из двух подмножеств Х α и Х β , вершины которых связаны между собой, но нет ни одной связи, соединяющей вершины самого подмножества Х α или Х β (рис. 4). Ориентированный граф G называют двудольным, если его неориенти- рованный двойник является двудольным графом. Сильносвязным называют такой граф, в котором для любых двух вершин Х i и Х j существует по крайней мере один путь (рис. 5, а ). х 2 х 2 х 2 х 3 х 1 х 3 х 1 х 3 х 1 х 5 х 6 х 5 х 4