Znajdowanie grubości grafu
Sformułowanie problemu.
Dane: graf
Szukane: grubość grafu
Przykładowe zastosowanie.
Przewodzącą płytkę, na której jednej stronie drukowane są części układu elektronicznego oraz przewody je łączące, nazywamy obwodem drukowanym. Projektując obwód drukowany należy pamiętać o tym, że przewody nie mogą się przecinać ponieważ nie są izolowane. Wynika stąd, że graf odpowiadający obwodowi drukowanemu musi być płaski. Rozpatrzmy graf, który odpowiada całemu układowi elektronicznemu. Wierzchołkami są elementy tego układu a krawędziami przewody. Grubość takiego grafu jest to minimalna liczba obwodów drukowanych potrzebnych do złożenia całego układu.
[ Początek strony ] [ MiNIWykłady ]
Wszystkie prawa zastrzeżone © 2000 Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej