Quem (e quando) definiu primeiro o intervalo dos gráficos?

7

Estive pesquisando referências no google scholar e reduzi a primeira menção para algo em torno de 1963 com um tremor muito estranho em 1949.

Então, eu estou tentando rastrear o artigo original, introduzindo gráficos de intervalo para citação, mas tem sido bastante elusivo até agora.

graph-theory reference-request history bitmask
fonte

Respostas:

5

Consegui rastrear as primeiras ocorrências de gráficos de intervalo até

G. Hajos, Über eine Art von Graphen , Int. Matemática. Nachr. 11 (1957) página 65

Esta referência refere-se a um livro de resumos (). No resumo de Hajos, os gráficos de intervalo são definidos, sem chamá-los de gráficos de intervalo . Além disso, ele diz que ele fornece condições se um gráfico é um gráfico de intervalo e discute como reconstruir os intervalos que definem o gráfico, quando o gráfico atende a essas condições.

A.Schulz
fonte
Como você localizou o artigo e verificou sua originalidade (em relação aos gráficos de intervalo)?
bitmask
Encontrei muitos documentos gráficos com intervalos citando essa fonte. Veja, por exemplo, o artigo de Fulkerson e Gross
A. Schulz
Na verdade, consegui encontrá-lo (página 34 --- 65 ---) e descreve o que chamamos de gráficos de intervalo, mas é um mero resumo. Não sei se você sabe ler alemão, mas basicamente afirma o problema de determinar se um determinado gráfico é um gráfico de intervalo. Parece genuíno, mas eu adoraria um artigo de verdade em vez de um resumo anunciando uma palestra. Você acha que esse artigo existe?
bitmask
@bitmask: Obrigado pelo link, eu o incluí no post. Além disso, como o alemão é minha língua materna, li o resumo e incluí um breve resumo.
precisa saber é o seguinte
Obrigado pela ajuda! Pedi ao nosso bibliotecário que tentasse desenterrar o artigo completo. Vou ver o que vem disso.
bitmask
2

Segundo Golumbic [1], Hajös propôs o seguinte problema em 1957 (tradução de Golumbic):

Dado um número finito de intervalos em uma linha reta, um gráfico associado a esse conjunto de intervalos pode ser construído da seguinte maneira: cada intervalo corresponde a um vértice do gráfico e dois vértices são conectados por uma aresta se e somente se o intervalos correspondentes se sobrepõem pelo menos parcialmente. A questão é se um dado gráfico é isomórfico para um dos gráficos que acabamos de caracterizar (Hajös [1957, p. 65, traduzido por MCG]).

Golumbic também discute como os gráficos de intervalo foram relacionados a uma pergunta em biologia feita por Benzer [2] em 1959.

[1] Golumbic, Martin Charles. Teoria algorítmica de grafos e gráficos perfeitos. Vol. 57. Elsevier, 2004.

[2] Benzer, Seymour. "Na topologia da estrutura genética fina." Anais da Academia Nacional de Ciências dos Estados Unidos da América 45.11 (1959): 1607.

Juho
fonte