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

- 21 - Если в графе G ( X,E ) множество вершин Х соответствует узлам решетки (сетки), а множество ребер Е – горизонтальным и вертикальным отрезкам, со- единяющим узлы решетки, то такой граф называют граф-решеткой. Расстояние между двумя различными вершинами x i ( a i ,b i ) и x j ( a j ,b j ) в гра- фе-решетке вычисляют по формуле: d ( x i ,x j ) = | a i –a j | + | b i –b j | . Наименьшее число ребер, которое следует удалить из графа G , чтобы он стал деревом, называется цикломатическим числом графа. γ( G ) = m − n + k, где n=|Х | – число вершин; m=|E| − число ребер; k – число компонентов связно- сти. Раскраской вершин графа G называется разбиение множества вершин Х на r непересекающихся подмножеств Х 1 ,Х 2 ,…,Х r таких, что X X i i =  ,  = j i X X Ø, а внутри X i нет смежных вершин. Наименьшее число подмножеств, на которое разбивается граф при его раскраске, называется хроматическим числом χ( G ). Практическое применение нашли двудольные графы (бихроматические графы). При разработке алгоритмов конструкторского и технологического про- ектирования ЭС возникает необходимость определения двудольности графа схемы или выделение максимально непересекающихся двудольных частей. Максимальное число вершин в несмежных подмножествах вершин графа G называется числом внутренней устойчивости. Многие задачи контроля ЭС сводятся к тождественным преобразованиям их моделей графов, которые в свою очередь приводят к переобозначению вер- шин и ребер. Такие графы называются изоморфными. Два графа G ( X,E ) и G' ( Х',Е' ) называются изоморфными, если можно уста- новить взаимно однозначное соответствие Х ↔ Х', Е ↔ Е ' такое, что если верши- ны x i ,x j ∈ X ↔ x' i ,x' j ∈ Х' , то ребро e ′ k =( x ′ i ,x ′ j ) ∈ E ′↔ e k =( x i ,x j ) ∈ E .