1

Что такое «электронная трассировка» и в чем заключается её смысл и алгоритм?

Дополнение: область знаний-математическая логика. К коду отношения не имеет, нужно определение, алгоритм, пример применения.

8
  • 2
    Уточните, пожалуйста ваш вопрос. Гугл такого понятия не знает. Нечто, сочетающее в себе термины "электронная трассировка" и "алгоритм" находится только в архиве какой-то фидошной эхи. Укажите хотя бы примерно область знаний, из которой взято это понятие.
    – fori1ton
    5 окт 2015 в 11:35
  • @fori1ton это проверка на планарность графа
    – user177221
    5 окт 2015 в 12:11
  • @PashaPash, а у меня вот сложилось впечатление, что не проверка на планарность, а укладка графа (вероятно, имеется ввиду разводка печатных плат). В любом случае, стоит дождаться уточнения автора вопроса.
    – fori1ton
    5 окт 2015 в 12:13
  • 1
    @fori1ton укладка графа - это и есть планарность. граф планарен == его можно уложить на плоскость
    – user177221
    5 окт 2015 в 12:14
  • rain.ifmo.ru/cat/view.php/theory/graph-coloring-layout/…
    – user177221
    5 окт 2015 в 12:15

1 ответ 1

6

Смысл электронной трассировки - проверка на возможность напечатать конктерную электронную схему на плоскости. Для этого граф, состоящий из вершин-компонентов и ребер-соединений, должен быть плоским.

Плоский граф — это граф, нарисованный таким образом, что его ребра не пересекаются. Говорят, что граф допускает плоскую укладку, если его можно нарисовать как плоский. Также плоские графы называют планарными.

По теореме Понтрягина-Куратовского: Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных K5 (звезда) или K3,3 (три дома, три колодца).

Для определения планарности графа можно использовать гамма-алгоритм. Или попробовать вручную перебрать все подграфы и проверить их на гомеоморфность.

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.