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.

Halin wurde 1962 an der Universität zu Köln bei Klaus Wagner promoviert („Über einen graphentheoretischen Basisbegriff und seine Anwendung auf Färbungsprobleme“) 1966 habilitierte er sich in Köln und 1971 wurde er Abteilungsdirektor und Professor an der Universität Hamburg. 1971/72 war er Gastprofessor an der Western Michigan University und 1977 an der Universität Aarhus.

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.

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, Journal of Geometry, Band 8, 1976, S. 171–186
  • Miscellaneous problems on infinite graphs, Journal of Graph Theory, Band 35, 2000, S. 128–151

Einzelnachweise

  1. ↑ Kürschners Gelehrtenkalender 2009
  2. ↑ Reinhard Diestel in Dmanet
  3. ↑ Rudolf Halin im Mathematics Genealogy Project (englisch)
  4. ↑ Weisstein, Halin graphs, Mathworld
  5. ↑ R. G. Parker, Halin graph, Encyclopedia of Mathematics, Springer
  6. ↑ Halin, S-functions for graphs, J. Geom., 8, 1976, 171–186
  7. ↑ Reinhard Diestel, Graphentheorie, Springer 2012, S. 308
  8. ↑ Bertelé, Brioschi, Nonserial Dynamic Programming, Academic Press 1972, dort Dimension genannt
  9. ↑ Robertson, Seymour: Graph minors III: Planar tree-width, Journal of Combinatorial Theory, Series B, Band 36, 1984, S. 49–64
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.