Student World

…

Problém čtyř barev nemá ve vztahu k IT význam pouze jako první matematický důkaz realizovaný pomocí počítače. Ze souvisejících zkoumání se vyvinuly techniky používané přímo při výrobě elektronických součástek – což je hezký příklad toho, jak i čistá věda může najít překvapivé praktické uplatnění.

…

Jak k tomu došlo? Důkazem zkoumání map neskončilo. Problém čtyř barev byl zformulován pro politické mapy států, jejichž území je „souvislé“. Tomu tak ale být nemusí; přirozeně přitom požadujeme, aby i navzájem oddělená území jednoho státu byla vybarvena stejnou barvou. Tím se ale situace značně komplikuje. Představme si třeba stav, kdy je jeden kontinent rozdělen mezi koloniální mocnosti, jejichž mateřské země se nacházejí na jiném kontinentu. Mapu mateřských zemí jsme úspěšně vybarvili čtyřmi barvami, ale když nyní odpovídající barvy použijeme pro kolonie, náhle spolu už stejně zbarvená území mohou sousedit. Kolik barev je potřeba v tomto případě, to kupodivu zatím nevíme. Matematici ale začali vymýšlet a analyzovat ještě podivnější případy, výrazně přesahující původní podobu problému.

Zkoumání map spadá do oboru matematiky zvaného teorie grafů. Mapa se totiž z určitých důvodů reprezentuje raději jako graf, kdy každému území odpovídá jeden bod (uzel). Pokud dvě území na mapě mají společnou hranici, pak jsou v grafu odpovídající body propojeny čárou (hranou). Graf je pak tedy kolekcí uzlů různě pospojovaných hranami do sítě.

Testování elektroniky

Výzkumníci Bellových laboratoří si všimli toho, že stejně tak si můžeme jako graf představit také tištěný spoj s elektronickými součástkami (následující výklad vychází z knihy matematických hádanek Iana Stewarta Jak rozkrájen dort). Poznatky z obarvování map pak našly přímé využití pro testování desek osazených elektronickými součástkami, tj. plošných/tištěných spojů.

Jedním z hlavním problémů elektroniky na čipu jsou „krátká spojení“ – tedy vodivá propojení prvků, které spolu propojeny být nemají. K chybě dochází především při nanášení vodivých spojů. Nanese-li se materiálu příliš mnoho, může se vytvořit i nežádoucí propojení. Odhalíme ho tak, že když k těmto dvěma prvkům přiložíme dva vodiče vycházející z baterie, obvod se uzavře a začne jím protékat elektrický proud, který můžeme detekovat.

Testování tištěného spoje hrubou silou je ovšem prakticky neproveditelné – museli bychom zjišťovat spojení každého prvku s každým. Jsou-li na desce řádově stovky prvků, bylo by pro jednu desku třeba udělat řádově statisíce testů. Poznatky teorie grafů ale umožňují řadu zjednodušení.

Především stojí za to si uvědomit, že nežádoucím způsobem propojené budou téměř výlučně součástky vedle sebe (je jedno, jak daleko nežádoucí spoj bude pokračovat, k vyřazení desky nám stačí odhalit jedinou závadu; v principu je samozřejmě možné, aby nechtěný spoj nějak divně zahýbal a propojil prvky nesousedící, prakticky však k tomu nedochází; spoje se totiž nanášejí vodorovně a svisle jako „rovné čáry“). Nyní si naši desku nakreslíme jako graf. Uzly grafu budou jednotlivé součástky, spojnice budou mezi těmi součástkami, které spolu sousedí (tyto „čáry“ se samozřejmě mohou různě křížit). Zkoumání tohoto typu grafu v souvislosti s luštěním úlohy čtyř barev ukázalo, že tento typ grafu lze obarvit vždy 12 různými barvami tak, aby žádné stejně zbarvené uzly nebyly spolu propojeny.

Nyní je už jasná základní logika celého postupu. Na grafu dostáváme 12 jednobarevných „sítí“. Protože uzly obarvené stejně odpovídají sítím, které neleží vedle sebe, nebudou mezi nimi existovat žádná vodivá spojení. Ta se mohou vyskytovat pouze mezi „různobarevnými“ sítěmi.

Pokud vyrábíme určitý typ desky, stačí nám tedy vyrobit „masky“, které padnou na jednotlivé sítě. Dále pak zkoumáme, zda nejsou vodivě propojeny jednotlivé tyto masky. Namísto testování spojení mezi stovkami součástek nám náhle stačí prověřit jen propojení 12 sítí. Navíc nemusíme ani zkoušet spojení všech se všemi; pokud například zjistíme, že sítě 1 a 2 jsou v pořádku v tom smyslu, že spolu nejsou propojeny, můžeme spolu vodivě spojit obě „masky“ a nyní dvojici sítí brát jako jeden celek a zkoušet ji spojovat s dalšími sítěmi.

Tímto způsobem sice nezjistíme, kde konkrétně se chyba nachází, ale to není ani potřeba – vadnou desku stačí prostě vyřadit, protože opravovat ji by bylo stejně příliš obtížné.

…

Úplná verze tohoto článku vychází v listopadovém čísle CIO-BusinessWorld. Toto číslo právě přichází na stánky.

autor Pavel Houser