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

- 18 - х 5 х 4 а ) б ) в ) Рис. 5 Слабосвязным называют такой граф, в котором для любых двух вершин Х i и Х j существует по крайней мере один маршрут (рис. 5, б ). Несвязный граф − такой, в котором существует хотя бы одна пара вершин, для которой нет марш- рута (рис. 5, в ). Квадратная таблица С =| |с ij || называется матрицей смежности, если ее эле- менты образуются по правилу:     − = . случае противном в0 с смежна вершина если 1, ; j i ij x х С Для неориентированного графа, представленного на рис. 3, б , матрица смежности выглядит следующим образом: x 1 x 2 x 3 x 4 x 5 x 6 x 1 0 1 0 1 0 1 x 2 1 0 1 0 0 0 C = x 3 0 1 0 1 1 1 x 4 1 0 1 0 1 0 x 5 0 0 1 1 0 1 x 6 1 0 1 0 1 0 В матрице инцидентности kn b B ij × = элементы b ij образуются по сле- дующему правилу:        = −= = концевой. является не если 0 дуги конец если 1 дуги начало если 1 i ij k i ij k i ij x , b ;e x , b ;e x , b Эйлеров граф – связный граф, в котором существует замкнутая цепь (цикл), проходящая через каждое его ребро только один раз (рис.6, в ). Полуэй- леров граф – если эта цепь не замкнута (рис.6, б ).