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

- 23 - Наименьшее значение r называется толщиной графа. Для многослойной платы – это количество слоев. Рис. 9 При решении задач САПР графу G ставят в соответствие гиперграф Н ( Х,Е ), который представляется в виде графа Кенига K ( X,E,V ), являющегося уже двудольным графом. Граф Кенига имеет два подмножества вершин Х и E и множество ре- бер V . Ребро в графе Кенига появляется, когда вершина x i инцидентна ребру е k . Вопросы для самоконтроля 1. Как задается граф G ( Х , Е ). 2. Какой граф называется ориентированным, неориентированным? 3. Что называется путем, маршрутом? 4. Как вычисляется длина (мощность) пути? 5. Как определяется локальная степень вершины графа G ( X,Е )? 6. Какой граф называется двудольным графом? 7. Какой граф называется сильносвязным, слабосвязным? 8. Перечислите особенности матрицы смежности. 9. Как составляется матрица инцидентности? 10.Какой граф называют гиперграфом. 11.Какой граф называется подграфом графа G ( X,E ). 5 x 4 x 2 x 3 x 1 x а ) 5 x 4 x 2 x 3 x 1 x б )