Das Problem, das ich im letzten Monat beschrieben habe, wird wohl kaum in absehbarer Zukunft aktuell werden: korrekte Färbung von Landkarten für Erde, Mond und Mars zusammen. Aber hinter der esoterischen Aufgabenstellung steckt nützliche Mathematik.

Anstelle der Karten selbst betrachtet man Graphen; das sind Diagramme, in denen sogenannte Knoten durch Linien, die Kanten des Graphen, verbunden sind. Für den Begriff der Dicke eines Graphen, der sich aus dem Erde-Mond-Problem ergab, haben Forscher bei den AT&T Bell-Laboratorien in Murray Hill (New Jersey) kürzlich eine interessante Anwendung gefunden. Es geht um die Fertigung gedruckter elektronischer Schaltungen.

Wie ich im letzten Monat erklärt habe, nennt man einen Graphen planar, wenn man ihn in der Ebene zeichnen kann, ohne daß sich irgendwelche Kanten kreuzen. Eine Stufe höher stehen Graphen der Dicke 2. Ihre Kanten kann man in zwei Mengen zerlegen, die jede einen planaren Graphen bilden (Bild 2). Ein Graph hat die Dicke 3, wenn man seine Kanten in drei Teilmengen zerlegen kann – und muß –, so daß jede von ihnen kreuzungsfrei ist, und so weiter.

Stellen Sie sich einen Graphen der Dicke 2 als Sandwich vor. Auf die untere Brotscheibe zeichnen wir – vielleicht mit Tomatenketchup – kreuzungsfrei die Kanten der ersten Menge und auf die obere die Kanten der zweiten Menge, ebenfalls kreuzungsfrei. Die Knoten werden zu vertikalen Linien; denken Sie an Partyspießchen, die durch alle Scheiben gestochen werden. (Sie müssen das Sandwich ja hinterher nicht aufessen.) Ein Graph, für den man d Brotscheiben braucht, hat die Dicke d (Bild 2).

Denken Sie sich nun eine elektrische Schaltung als Graphen. Die Knoten sind die Bauteile und die Kanten die elektrischen Verbindungen zwischen ihnen. Wenn sie alle als gedruckte Schaltung auf der Oberfläche einer Leiterplatine verlaufen sollen, muß der Graph planar sein, denn jede Überkreuzung ergäbe einen Kurzschluß. Wenn man beide Seiten der Platine nutzt, kann man Graphen der Dicke 2 realisieren: Die Platine ist der Käse, und die gedruckten Schaltungen sind die Brotscheiben (samt Ketchup). Mit mehreren Platinen läßt sich die Dicke des Graphen weiter steigern. Ähnliche Überlegungen gelten für die Siliciumchips, die in den Computern stecken, denn auch sie werden aus Schichten aufgebaut.

Eine typische Platine hat ungefähr 100¥100 Löcher, durch welche die Anschlüsse der Bauteile gesteckt werden, angeordnet in einem quadratischen Gitter. Manche dieser Löcher sind durch horizontal und vertikal verlaufende Leiterbahnen miteinander verbunden. Wenn durch Fabrikationsfehler überzählige Verbindungen entstehen, ist die Platine unbrauchbar und muß ausgesondert werden. Wie findet man möglichst schnell die defekten Exemplare?

Häufig sind zahlreiche Anschlüsse miteinander zu einem sogenannten Netz verbunden. (Ein solches Netz hat allerdings keine Maschen, das heißt geschlossene Rundwege; denn wenn es einen solchen gäbe, könnte man ihn schadlos durch Weglassen eines Leitungsstücks aufbrechen.) Es geht also darum, festzustellen, ob irgendwo zwei verschiedene Netze durch einen Kurzschluß miteinander verbunden sind.

Nichts einfacher als das: Man lege eine Spannung an beide Netze und ein Anzeigegerät (zum Beispiel eine Glühbirne) in den Stromkreis (Bild 1). Ein Kurzschluß macht sich dadurch bemerkbar, daß die Glühbirne aufleuchtet.

Den Prozeß kann man automatisieren und dadurch erheblich beschleunigen; aber das würde nichts daran ändern, daß jedes Netz gegen jedes andere zu testen ist. Bei n Netzen sind das n(n–1)/2 Versuche oder 125000 für die typische Anzahl von 500 Netzen in einer Schaltung, und das sind viel zu viele.

Die Graphentheorie verhilft hier zu enormen Einsparungen. Die Zahl der Tests läßt sich auf bloße 11 drücken, und mit etwas mehr Nachdenken sogar auf 4.

Zunächst verwandelt man die gedruckte Schaltung in einen Graphen, der die Informationen über mögliche Kurzschlüsse deutlicher zum Vorschein bringt. Nennen wir ihn den Netzgraphen des Schaltkreises (Bild 4); denn jedem Netz wird ein Knoten zugeordnet.

Die Kanten des Netzgraphen repräsentieren potentielle Kurzschlüsse. Und zwar verbinden wir genau dann zwei Knoten des Netzgraphen durch eine Kante, wenn die zugehörigen Netze benachbart sind, das heißt, wenn sie durch eine horizontale oder vertikale Linie verbunden werden können, die kein weiteres Netz trifft.

Im Prinzip könnte ein Kurzschluß zwar auch zwischen nichtbenachbarten Netzen entstehen. Aber praktisch alle solchen Kurzschlüsse betreffen auch die dazwischenliegenden Netze. Typischerweise werden nämlich in einem Herstellungsschritt die horizontalen Verbindungen gelegt, in einem zweiten die vertikalen. Kurzschlüsse entstehen, indem an einer Stelle zu viel leitendes Material aufgebracht wird: Webfehler sozusagen. (Von weiteren möglichen Fehlern soll hier nicht die Rede sein, weil sie viel seltener sind.) Ein solcher Fehler macht sich schon dann bemerkbar, wenn man nur nach Kurzschlüssen zwischen benachbarten Netzen sucht.

Ich habe oben bemerkt, daß der Graph für eine beidseitig gedruckte Schaltung die Dicke 2 hat, eine Ebene für jede Seite. Der Netzgraph hat auch die Dicke 2, aber aus einem anderen Grund: In dem einen Teilgraphen versammelt man alle Kanten, die zu horizontalen Kurzschlußverbindungen gehören, in dem anderen die zu den vertikalen. Nach einem Satz des englischen Mathematikers Percy John Heawood (1861 bis 1955) läßt sich jeder Graph der Dicke 2 mit 12 Farben färben. Nicht nur die im letzten Monat beschriebene Karte von Erde und Mond, sondern auch der Netzgraph jeder gedruckten Schaltung ist mit 12 Farben so färbbar, daß in keinem Falle benachbarte Netze die gleiche Farbe tragen.

Da wir nach Kurzschlüssen zwischen benachbarten Netzen suchen, können wir unsere Suche auf Paare verschiedenfarbiger Netze beschränken. Also verbinden wir zunächst jeweils alle Netze gleicher Farbe mit einer Sonde, einem geeignet konstruierten Drahtbaum, den wir auf die Platine aufsetzen. Wenn wir nun etwa Blau gegen Gelb auf Kurzschluß testen wollen, setzen wir die blaue und die gelbe Sonde auf die Platine, schalten eine Batterie und ein Lämpchen in Reihe mit den Sonden und sehen nach, ob ein Strom fließt (Bild 3 links). Wenn irgendwo ein Webfehler ein blaues mit einem gelben Netz verbindet, leuchtet das Lämpchen auf. Dieser Test sagt uns nicht, wo auf der Platine der Fehler liegt. Da wir aber fehlerhafte Platinen nur aussondern und nicht reparieren wollen, interessiert uns das auch nicht.

Um nun einen beliebigen Webfehler festzustellen, braucht man nur alle Paare von Sonden gegeneinander zu testen. Es gibt 12 Sonden, also 12¥11/2=66 solche Paare. Statt 125000 oder mehr Tests brauchen wir also nur noch 66 – ein beachtlicher Fortschritt.

Aber es geht noch besser. Dazu testen wir Sonde 1 gegen Sonde 2 und werfen alle Platinen weg, die diesen Test nicht bestehen. Dann verbinden wir die Sonden 1 und 2 leitend miteinander und testen sie gemeinsam gegen Sonde 3, werfen wieder alle Platinen weg, bei denen das Lämpchen aufleuchtet, und so weiter. So kommen wir mit nur 11 Tests aus (Bild 3 rechts).

Allen J. Schwenk von der Universität von West-Michigan in Kalamazoo bemerkte, daß man die Anzahl der Tests noch weiter drücken kann. Dazu schreibe man die Zahlen von 1 bis 12 in Binärdarstellung, 0001 bis 1100, und numeriere die Sonden entsprechend. Sodann verbinde man alle Sonden, deren Binärdarstellung an erster Stelle eine Null hat, miteinander zu einer Supersonde, desgleichen alle Sonden mit einer Eins an erster Stelle. Nun teste man, ob diese Supersonden in Kontakt stehen. Wenn ja, werfe man die Platine weg. Wenn nein, schalte man die Sonden auf andere Weise zu Supersonden zusammen; und zwar ist diesmal die zweite Binärziffer maßgebend. Ebenso verfahre man mit der dritten und der vierten Binärziffer.

Das war’s schon. Wieso? Wenn es einen Kurzschluß gibt, verbindet er Sonden miteinander, deren Binärdarstellungen sich an wenigstens einer Stelle unterscheiden. Folglich wird einer der vier Tests den Fehler finden.

Eine Reduktion von 125000 Tests auf bloße vier pro Platine zahlt sich ab einer gewissen Stückzahl zweifellos aus. Schließlich muß man die komplizierten Sonden für jeden Schaltkreisentwurf nur einmal bauen.

Von einem weltfernen Kartographenproblem sind wir ausgegangen und bei einem kostensparenden Test für gedruckte Schaltungen angelangt. In der Mathematik kommt es eben meist nicht auf eine bestimmte Realisierung einer Idee an, sondern auf die Wege, die sie eröffnet, wenn man sie gekonnt und mit Phantasie verfolgt.


Literaturhinweis

Coloring Ordinary Maps, Maps of Empires, and Maps of the Moon. Von Joan P. Hutchinson in: Mathematics Magazine, Band 66, Heft 4, Seiten 211 bis 225, Oktober 1993.



Aus: Spektrum der Wissenschaft 6 / 1998, Seite 10
© Spektrum der Wissenschaft Verlagsgesellschaft mbH