Составители:
Рубрика:
95
При построении матрицы смежности для направленного графа d
(см. рис. 5.2) каждой строке сопоставляется вершина, из которой вы
ходит стрелка, а каждому столбцу – вершина, в которую входит стрел
ка (табл. 5.12). Матрицы смежности для направленного графа не яв
ляются симметричными относительно главной диагонали, и поэтому
они не сжимаются до треугольных таблиц.
5.4. Понятие о плоских графах –
«Задача о трех домах и трех колодцах»
Рассмотрим простую головоломку, которая называется «Задача о
трех домах и трех колодцах». Три друга получили садовые участки и
начали строить дома. Сначала выкопали три колодца и ходили к лю
бому из них. Когда же дома были построены, приехали домочадцы и,
как часто бывает, перессорились. И потребовали, чтобы хозяева сде
лали дорожки так, чтобы от любого дома можно было бы дойти до лю
бого колодца, но дорожки не должны были пересекаться, чтобы домо
чадцы не встречались на пути к колодцам. Можно ли удовлетворить
требования домочадцев?
Все попытки удовлетворить требования домочадцев заканчивают
ся неудачно (рис. 5.3). Почему? Потому, что этот граф невозможно на
плоскости изобразить так, чтобы его ребра не пересекались. Этот граф
не является плоским.
Вопрос о том, является ли граф плоским или нет – исключитель
но важен для технологии интегральных микросхем. Ведь каждая
микросхема представляет собой некоторый граф, в котором имеют
ся контактные площадки (вершины) и связи (ребра).
Задача может ставиться так: имеется новая схема (например, про
цессора). На какое минимальное число фрагментов ее нужно разбить,
чтобы каждый фрагмент мог быть представлен плоским графом?
Рис. 5.3. «Задача о трех домах и трех колодцах»
Страницы
- « первая
- ‹ предыдущая
- …
- 93
- 94
- 95
- 96
- 97
- …
- следующая ›
- последняя »
