Реферат: Методы размещения и трассировки печатных плат на примере модуля памяти
4) Из списка рёбер выбираем следующее по очереди ребро.
5) Если обе вершины выбраного ребра уже есть в списке проведённых ребер, вычёркиваем это ребро из списка и возвращаемся к п. 4.
Если же одна (и только одна!) из вершин выбраного ребра уже участвует в связи (присутствует как вершина в списке проведённых рёбер), то проводим это ребро, иначе возвращаемся к п. 4.
6) Повторяем пункты 4-5 до тех пор, пока список рёбер не опустеет.
Проведём трассировку цепи питания +5В.
Выпишем список всех возможных рёбер, сразу откидывая ребро, если в списке уже есть ребро с такими же вершинами.
1-2 1-3 1-4 1-5 1-6 1-7 1-8 1-9 1-10 1-11 1-12 1-13 1-14
2-3 2-4 2-5 2-6 2-7 2-8 2-9 2-10 2-11 2-12 2-13 2-14
3-4 3-5 3-6 3-7 3-8 3-9 3-10 3-11 3-12 3-13 3-14
4-5 4-6 4-7 4-8 4-9 4-10 4-11 4-12 4-13 4-14
5-6 5-7 5-8 5-9 5-10 5-11 5-12 5-13 5-14
6-7 6-8 6-9 6-10 6-11 6-12 6-13 6-14
7-8 7-9 7-10 7-11 7-12 7-13 7-14
8-9 8-10 8-11 8-12 8-13 8-14
9-10 9-11 9-12 9-13 9-14
10-11 10-12 10-13 10-14
11-12 11-13 11-14
12-13 12-14
13-14
Упорядочим этот список в порядке увеличения длинны рёбер. Полученый список запишем построчно:
5-6 6-11 11-12 4-7 7-10 10-13 3-8 8-9 9-14 1-2 2-3 3-4 4-5
7-8 6-7 9-10 10-11 12-13 13-14 5-11 6-12 4-7 7-13 3-9 8-14 2-4
3-5 6-8 9-11 12-14 1-8 1-9 1-14 3-7 5-7 4-6 4-8 6-10 7-11
9-7 8-10 11-13 10-12 10-14 9-13 2-8 2-7 3-6 5-8 8-11 6-9 9-12
11-14 5-10 6-13 4-9 7-14 7-12 4-11 3-10 8-13 2-9 2-14 3-13 4-14
4-12 5-13 1-4 1-7 1-10 1-13 1-5 1-6 2-13 3-11 5-9 8-12 6-14
2-5 2-6 2-11 3-12 5-14 2-12
Проводим первую связь 5-6. Следующее ребро имеющее общую точку – 6-11. Проводим и его. Проводим следующее ребро 11-12.
Следующее проведённое нами ребро 4-5, затем 4-7, 7-10 и 10-13. Теперь 3-4 и 3-8, 8-9 и 9-14.
Затем проводим рёбро 2-3 и наконец 1-8.
Цепь разведена, поскольку все возможные вершины уже присутствуют в списке проведённых рёбер. Рисунок проведённых дорожек приведёна на рис.3.2.
| Å | 5 | Å | Å | 6 | Å | Å | 11 | Å | Å | 12 | Å | ||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | DD10 | Å | Å | DD11 | Å | Å | DD13 | Å | Å | DD12 | Å | ||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | 4 | Å | Å | 7 | Å | Å | 10 | Å | Å | 13 | Å | ||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | DD9 | Å | Å | DD8 | Å | Å | DD6 | Å | Å | DD7 | Å | ||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | 3 | Å | Å | 8 | Å | Å | 9 | Å | Å | 14 | Å | ||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | DD5 | Å | Å | DD2 | Å | Å | DD3 | Å | Å | DD4 | Å | ||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | 2 | Å | |||||||||||||
| Å | Å | ||||||||||||||
| Å | Å | ||||||||||||||
| Å | DD1 | Å | |||||||||||||
| Å | Å | ||||||||||||||
| Å | Å | ||||||||||||||
| Å | Å | ||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | Å | Å | Å | Å | Å | Å | ||