Rudolf Halin

Rudolf Halin (* 3. Februar 1934 in Uerdingen; † 7. November 2014 in Mölln) war ein deutscher Mathematiker, der sich mit Graphentheorie und speziell mit unendlichen Graphen befasste.

Rudolf Halin, Sohn von Margarethe Halin, geborene Limmer, und des Studienrats Wilhelm Halin, wurde 1934 in Uerdingen bei Krefeld geboren. Er war evangelisch, besuchte ein Gymnasium in Uerdingen und studierte an der Universität Köln Mathematik. Dort absolvierte er 1960 das Staatsexamen und wurde 1962 bei Klaus Wagner zum Dr. rer. nat. promoviert (Titel seiner Dissertation: Über einen graphentheoretischen Basisbegriff und seine Anwendung auf Färbungsprobleme). 1966 habilitierte er sich in Köln, wo er seine Lehrtätigkeit begann. 1971 wurde er Abteilungsdirektor und Professor für Mathematik an der Universität Hamburg. 1971/72 war er Gastprofessor an der Western Michigan University in den USA und 1977 an der Universität Aarhus.

Im Jahr 1964 definierte er Enden in unendlichen Graphen als Äquivalenzklassen unendlich langer Wege (Untergraphen in denen ein Knoten den Grad 1 hat und der Rest Grad 2, zwei Wege sind äquivalent falls ein dritter existiert der unendlich viele Knoten von beiden enthält). 1965 bewies er seinen Gittersatz (Halin’s grid theorem), der besagt, dass unendliche ebene Graphen mit dicken Enden (das heißt Enden mit unendlich vielen paarweise disjunkten Wegen) genau solche sind, die Untergitter des ebenen Hexagonalgitters enthalten.

Nach ihm sind Halin-Graphen benannt, die er 1971 studierte. Sie sind eben und entstehen aus Bäumen mit mindestens vier Knoten, von denen keiner den Grad 2 hat, indem die Blätter des Baums durch einen Zyklus verbunden werden. Die Graphen erhalten Bedeutung dadurch, dass viele algorithmische Probleme auf ihnen effizient lösbar sind, auf allgemeinen planaren Graphen aber nicht.

Beispiel eines Halin-Graphen, entstanden aus dem blau gezeichneten Baum

1974 erweiterte er den Satz von Menger auf unendliche Graphen.

1976 führte er (unter anderem Namen) die Begriffe Baumzerlegung und Baumweite ein. Unter anderem Namen wurde der Begriff schon 1972 von Umberto Bertelé und Francesco Brioschi eingeführt und erneut unabhängig von Neil Robertson und Paul Seymour 1984 in ihrer Arbeit zum Minorentheorem.

2000 veröffentlichte er eine Liste offener Probleme über unendliche Graphen.

Schriften

• Graphentheorie, 2 Bände, Erträge der Forschung, Wissenschaftliche Buchgesellschaft 1980, 1981, 2. Auflage in einem Band 1989
• Über unendliche Wege in Graphen, Mathematische Annalen, Band 157, 1964, S. 125–137
• Über die Maximalzahl fremder unendlicher Wege in Graphen, Mathematische Nachrichten, Band 30, 1965, S. 63–85
• Studies on minimally n-connected graphs, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), London: Academic Press, 1971, S. 129–136 (Halin Graphen)
• A note on Menger’s theorem for infinite locally finite graphs (= Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. Band 40). 1974, S. 111–114.
• S-functions for graphs. In: Journal of Geometry. Band 8, 1976, S. 171–186
• Miscellaneous problems on infinite graphs. In: Journal of Graph Theory. Band 35, 2000, S. 128–151.

Literatur

• Halin, Rudolf. In: Walter Habel (Hrsg.): Wer ist wer? Das deutsche Who’s who. 24. Ausgabe. Schmidt-Römhild, Lübeck 1985, ISBN 3-7950-2005-0, S. 445.

Weblinks

• Rudolf Halin im Hamburger Professorinnen- und Professorenkatalog
• Rudolf Halin in der Datenbank zbMATH