Wer (und wann) hat zuerst Intervallgraphen definiert?

7

Ich habe Google Scholar nach Referenzen durchsucht und die erste Erwähnung auf irgendwo um 1963 mit einem sehr seltsamen Jitter im Jahr 1949 eingegrenzt.

Ich versuche also, das Originalpapier aufzuspüren, in dem Intervalldiagramme zum Zitieren eingeführt werden, aber es war bisher ziemlich schwer fassbar.

graph-theory reference-request history Bitmaske
quelle

Antworten:

5

Ich konnte die ersten Vorkommen von Intervallgraphen bis zu verfolgen

G. Hajos, Über eine Kunst von Graphen , Int. Mathematik. Nachr. 11 (1957) Seite 65

Diese Referenz bezieht sich auf ein Buch mit (Gesprächs-) Abstracts. In der Zusammenfassung von Hajos werden Intervallgraphen definiert, ohne sie tatsächlich als Intervallgraphen zu bezeichnen . Darüber hinaus heißt es, dass er Bedingungen angibt, ob ein Graph ein Intervallgraph ist, und er diskutiert, wie die Intervalle, die den Graph definieren, rekonstruiert werden, wenn der Graph diese Bedingungen erfüllt.

A.Schulz
quelle
Wie haben Sie das Papier aufgespürt und seine Originalität überprüft (in Bezug auf Intervalldiagramme)?
Bitmaske
Ich fand viele Intervalldiagramme, in denen diese Quelle zitiert wurde. Siehe zum Beispiel das Papier von Fulkerson und Gross
A.Schulz
Ich habe es tatsächlich geschafft, es zu finden (Seite 34 --- 65 ---), und es beschreibt, was wir Intervallgraphen nennen, aber es ist nur eine Zusammenfassung. Ich weiß nicht, ob Sie Deutsch lesen können, aber es gibt im Grunde das Problem an, festzustellen, ob ein gegebener Graph ein Intervallgraph ist. Es scheint echt zu sein, aber ich hätte eine echte Zeitung geliebt, anstatt eine abstrakte Werbung für einen Vortrag. Glaubst du, dass es so ein Papier überhaupt gibt?
Bitmaske
@bitmask: Danke für den Link, ich habe ihn in den Beitrag aufgenommen. Da Deutsch meine Muttersprache ist, habe ich das Abstract gelesen und eine kurze Zusammenfassung beigefügt.
A.Schulz
Danke für Ihre Hilfe! Ich bat unseren Bibliothekar, das ganze Papier auszuheben. Ich werde sehen, was daraus entsteht.
Bitmaske
2

Laut Golumbic [1] schlug Hajös 1957 das folgende Problem vor (Übersetzung von Golumbic):

Bei einer endlichen Anzahl von Intervallen auf einer geraden Linie kann ein mit diesem Satz von Intervallen verknüpfter Graph auf folgende Weise konstruiert werden: Jedes Intervall entspricht einem Scheitelpunkt des Graphen, und zwei Scheitelpunkte sind genau dann durch eine Kante verbunden, wenn die entsprechende Intervalle überlappen sich zumindest teilweise. Die Frage ist, ob ein gegebener Graph zu einem der gerade charakterisierten Graphen isomorph ist (Hajös [1957, S. 65, übersetzt von MCG]).

Golumbic diskutiert auch, wie Intervallgraphen mit einer Frage in der Biologie zusammenhängen, die Benzer [2] 1959 gestellt hat.

[1] Golumbic, Martin Charles. Algorithmische Graphentheorie und perfekte Graphen. Vol. 57. Elsevier, 2004.

[2] Benzer, Seymour. "Zur Topologie der genetischen Feinstruktur." Verfahren der Nationalen Akademie der Wissenschaften der Vereinigten Staaten von Amerika 45.11 (1959): 1607.

Juho
quelle