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

- 19 - Конечный граф будет эйлеровым, если он связан и все его локальные сте- пени вершин четные. Связный граф является полуэйлеровым, если в нем не бо- лее двух вершин имеют нечетные локальные степени. Рис.6 Униграфом называется такой граф, у которого каждой паре вершин соот- ветствует не более одного ребра. У мультиграфа есть хотя бы одна пара вер- шин, которым соответствует несколько ребер. Звездный граф – такой граф, множество вершин Х которого содержит не- которую вершину x j , с которой смежные все другие вершины графа (рис. 7). При конструировании ЭС за множество вершин Х принимают множество элементов схемы, а за множество ребер Е – множество цепей. Такой граф назы- вают гиперграфом. В графе G (рис. 8, а ) можно выделить подграфы. Подграфом G i ( X i ,E i ) графа G ( X,E ) называется граф, у которого все вер- шины и ребра принадлежат графу G , то есть X i ⊆ X, E i ⊆ E . Чтобы получить под- граф, достаточно удалить из графа G любую вершину с инцидентными ей реб- рами (рис. 8, б ). Суграфом G ' ( Х',Е' ) графа G ( X,E ) называется граф, у которого Х'=Х, E ′ ⊆ Е. Чтобы получить суграф достаточно удалить одно ребро из графа (рис. 8, в ). 5 x 4 x 2 x 3 x 1 x а ) 1 x 2 x 3 x 4 x 5 x б ) 1 x 2 x 3 x 4 x 5 x 6 x 7 x в )