Дискретная математика. Кулаков Ю.В - 45 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Основываясь на критерии Понтрягина, можно получить еще один критерий
планарности. Этот критерий использует понятие элементарного стягивания, заключающегося в сле-
дующем. При стягивании любого ребра {a, b} графа оно исчезает, а вершины, коинцидентные этому
ребру, отождествляются (рис. 23). Полученная таким образом вершина коинцидентна тем же ребрам,
что и a, b (кроме ребра, которое выброшено).
Теорема. Граф планарен тогда и только тогда, когда он не содержит под-
графа или частичного графа, стягиваемых к F
5
или K
3, 3
.
Рассмотрим задачу проектирования печатной схемы электронного устройст-
ва. При проектировании такой схемы соединительные провода наносят печатным способом на плоскую
поверхность изоляционного материала. Печатные проводники не изолированы и поэтому не должны
пересекаться. Если граф электронного устройства, в котором роль вершин играют приборы, а ребер –
соединительные проводники, является планарным, то печать проводников может быть выполнена на
одной плоскости.
В том случае, когда граф не планарный, печать осуществляется на нескольких плоскостях, число кото-
рых определяется числом скрещиваний (толщиной) графа – наименьшим возможным числом пересече-
ний при изображении графа на плоскости.
Толщиной t(G) графа G называется наименьшее число планарных графов,
объединение которых дает G. Толщина планарного графа равна 1. Толщина графа G = <V, U> определя-
ется неравенством
t(G) ≥ 1 +
−
−
∑
=
)2(6
2
1
n
s
n
i
i
,
где
][
– целая часть; n – мощность множества V; s
i
– степень i-й вершины.
Рассмотрим граф электронного устройства, изображенный на рис. 24, а. Опре-
делим, является ли этот граф планарным, и если нет, то выясним, сколько потребуется слоев при изго-
товлении печатной схемы и какие ребра графа следует удалить, чтобы граф стал планарным.
Согласно критерию Понтрягина этот граф является непланарным, поскольку
содержит запрещенные фигуры: частичный подграф и подграф, гомеоморфные графу F
5
(рис. 25, а, в), и
подграфы, гомеоморфные графу K
3, 3
(рис. 25, б, г).
1
2
3
7
6
5
4
а)
1
2
3
7
6
5
4
б)
Рис. 24

Страницы