Дискретная математика. Громов Ю.Ю - 63 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

63
Рассмотрим задачу проектирования печатной схемы электронного
устройства. При изготовлении такой схемы соединительные проводники
наносят печатным способом на плоскую поверхность изоляционного мате-
риала. Эти проводники не изолированы и поэтому не должны пересекать-
ся. Если граф электронного устройства, в котором роль вершин играют вы-
воды приборов, а роль рёбер – соединительные проводники, является пла-
нарным, то печать проводников может быть выполнена на одной плоско-
сти. В противном случае печать проводников осуществляется на несколь-
ких плоскостях, число которых определяется толщиной этого графа.
Предположим, что граф G, изображённый на рис. 28, а, является гра-
фом некоторого электронного устройства. Определим, является ли этот
граф планарным или непланарным. Если граф G окажется непланарным, то
выясним, сколько потребуется плоскостей для нанесения проводников при
изготовлении печатной схемы соответствующего устройства.
Согласно критерию Понтрягина этот граф является непланарным,
поскольку содержит запрещённые фигуры: частичный подграф и под-
граф, гомеоморфные графу F
5
(рис. 29, а, в), и подграфы, гомеоморфные
графу K
3, 3
(рис. 29, б, г).
Заметим, что графы на рис. 29, а и б преобразуются в графы, изо-
морфные графам F
5
и K
3, 3
, в результате замены цепей ({4, 5}, {5, 7})
рёбрами {4, 7}. Граф на рис. 29, в преобразуется в граф, изоморфный
графу F
5
, при замене цепи ({1, 7}, {7, 5}) ребром {1, 5} и последующем
стягивании ребра {1, 2}. Граф на рис. 29, г преобразуется в граф, изоморф-
ный графу K
3, 3
, в результате замены цепи ({1, 2}, {2, 4}) ребром {1, 4}.
Оценим толщину рассматриваемого графа G:
t(G) ≥ 1 +
−
−
)27(6
232
= 2, t(G) ≥ 2.
Чтобы определить, какие рёбра графа G следует удалить для преоб-
разования его в планарный граф, необходимо выделить все содержащие-
ся в нём запрещённые фигуры Q
1
, Q
2
, ..., Q
m
и построить двумерную таб-
1
2
3
7
6
5
4
а)
1
2
3
7
6
5
4
б)
Рис. 28

Страницы