Don't take life too seriously: it's just a temporary situation

Nel 1960 Antony Hill propose il problema di determinare il numero di incroci di un grafo, cioè il minimo numero di incroci necessari se lo si disegna sul piano, collegando i nodi con curve arbitrarie.

 

M.R. Garey e D.S. Johnson dimostrarono nel 1983 che determinare il numero minimo di incroci per un grafo generico è un problema che appartiene a una categoria di problemi, chiamati NP-completi, per i quali sono noti solo algoritmi la cui complessità cresce esponenzialmente col numero di oggetti trattati (in questo caso nodi e archi).

Il problema resta NP-completo anche se ci si limita a grafi trivalenti, nei quali ogni nodo è connesso ad altri tre.

 

Un teorema importante garantisce che se il grafo non contiene più archi che connettano la stessa coppia di nodi, né archi che connettano un nodo a se stesso, se il numero di archi a è almeno 15 / 2 volte il numero di nodi n, allora il numero di incroci è almeno Limite inferiore per il numero di incroci, mentre se il numero di archi a è almeno c volte il numero di nodi n, allora il numero di incroci è almeno Limite inferiore per il numero di incroci (M. Ajtai, V. Chvátal, M. Newborn e E. Szemerédi, 1982 e indipendentemente T. Leighton, 1983).

 

Se il grafo viene disegnato su superfici non equivalenti al piano, il numero di incroci in generale scende, ma non si conoscono formule generali.

 

Se il grafo viene tracciato utilizzando solo segmenti aventi i nodi per estremi, invece di curve arbitrarie, il numero minimo di incroci necessari si chiama “numero di incroci rettilinei” del grafo.

 

Nel caso del grafo completo con n nodi, cioè di un grafo nel quale ogni nodo è collegato con un segmento a ciascun altro, i numeri di incroci per i primi valori di n sono riportati nella tabella seguente.

n

Incroci sul piano In

Incroci rettilinei In

Incroci sul toro

1

0

0

0

2

0

0

0

3

0

0

0

4

0

0

0

5

1

1

0

6

3

3

0

7

9

9

0

8

18

19

4

9

36

36

9

10

60

62

23

11

100

102

42

12

150

153

70

13

I13 ≤ 225

229

105

14

I14 ≤ 315

324

154

15

I15 ≤ 441

447

226

16

I16 ≤ 588

603

326

17

 

798

 

18

 

1029

 

19

 

1318

 

20

 

1657

 

21

 

2055

 

22

 

2528

 

23

 

3077

 

24

 

3699

 

25

 

4430

 

26

 

5250

 

27

 

6180

 

28

 

7233 ≤ I28 ≤ 7234

 

29

 

7393 ≤ I29 ≤ 8427

 

30

 

8531 ≤ I30 ≤ 9745

 

 

Non è semplice trovare ladisposizione dei nodi che permette di ridurre al minimo il numero di incroci; per esempio, il grafo completo a 4 nodi richiede un incrocio, se i nodi sono ai vertici di un quadrato, come nel disegno seguente.

 

Grafo completo con 4 nodi, tracciato con un incrocio

 

L’incrocio può però essere eliminato se i nodi sono disposti come nel disegno seguente.

 

Grafo completo con 4 nodi, tracciato senza incroci

 

 

Analogamente il grafo completo a 5 nodi richiede 5 incroci, se i punti sono disposti ai vertici di un pentagono, producendo la familiare figura a stella, ma gli incroci si riducono a uno, se i nodi sono disposti come nel disegno seguente, anche se serve un attimo di riflessione per verificare che i due grafi sono isomorfi.

 

Grafo completo con 4 nodi, tracciato con un incrocio

 

 

Com’è ragionevole attendersi, se si possono tracciare linee curve, il numero di incroci in generale si riduce, tuttavia un grafo completo deve avere almeno 8 nodi perché sia possibile risparmiare un incrocio.

 

D.Bienstock e N. Dean dimostrarono nel 1993 che se il numero minimo di incroci non supera 3, il grafo può essere tracciato con segmenti senza aumentare il numero di incroci, ma che si possono costruire grafi che richiedono solo 4 incroci, se tracciati con curve, ma un numero arbitrariamente grande se tracciati con segmenti (D. Bienstock e N. Dean, 1992).

 

Richard K. Guy dimostrò nel 1973 che tracciando curve bastano Limite superiore per il numero di incroci per un grafo completo con n nodi incroci per un grafo completo con n nodi e congetturò che questo sia il numero minimo di incroci richiesti per ogni valore di n. Guy stesso dimostrò nel 1974 la congettura per i valori di n fino a 10 e Pan e Richter la dimostrarono nel 2007 per n sino a 12.

La formula di Guy diviene per Limite superiore per il numero di incroci per un grafo completo con n nodi, per n pari n pari e Limite superiore per il numero di incroci per un grafo completo con n nodi, per n dispari per n dispari e al crescere di n tende a Limite superiore asintotico per il numero di incroci per un grafo completo con n nodi.

La formula di Guy fornisce un limite superiore, mentre è noto che servono almeno Limite inferiore per il numero di incroci per un grafo completo con n nodi incroci.

 

Se ci si limita a segmenti, H.F. Jensen e indipendentemente Eggleton dimostrarono nel 1971 che bastano Limite superiore per il numero di incroci rettilinei per un grafo completo con n nodi incroci e D. Singer dimostrò nel 1971 che ne bastano Limite superiore per il numero di incroci rettilinei per un grafo completo con n nodi , mentre Bernardo Ábrego e Silvia Fernández-Merchand dimostrarono nel 2003 che sono necessari almeno gli incroci indicati dalla formula di Guy.

L. Lovász, K. Vesztergombi, U. Wagner ed E. Welzl dimostrarono nel 2004 che per n abbastanza grande sono necessari più incroci di quanti ne servano tracciando curve. (v. costante degli incroci rettilinei). Non è però stato dimostrato che ciò avvenga per tutti i grafi completi con 10 o più nodi, come tutti gli esperti ritengono.

Per confronto, se si dispongono n nodi su una circonferenza, in modo da evitare incroci multipli (punti nei quali si incrociano più di due segmenti), il numero di incroci è Numero di incroci rettilinei per un grafo completo con n nodi, se si dispongono i nodi su una circonferenza, perché ogni quaterna di nodi distinti contribuisce con un incrocio; asintoticamente questo numero tende a 8 / 3 volte il limite superiore dimostrato da Guy.

 

Un grafo bipartito è un grafo nel quale i nodi sono suddivisi in due insiemi e ogni arco connette un nodo di un insieme a uno dell’altro. Una definizione equivalente è un grafo che non contiene cicli di lunghezza dispari.

Un grafo bipartito completo è un grafo nel quale ogni nodo di un insieme è connesso da archi a tutti i nodi dell’altro.

La congettura di Zarankiewicz afferma che se si disegna sul piano un grafo bipartito completo con n nodi in un insieme e m nell’altro, il minimo numero di incroci è Numero minimo di incroci per un grafo bipartito completo con n nodi in un insieme e m nell’altro, secondo la congettura di Zarankiewicz.

Zarankiewicz dimostrò nel 1954 che la formula rappresenta un limite superiore. La dimostrazione originale conteneva alcuni errori, in seguito corretti.

La congettura è stata dimostrata per tutti i valori di n e m non superiori a 7 e in vari casi particolari.

 

Il problema è stato affrontato anche per altre superfici, ma risolto solo in pochi casi:

  • il numero minimo di incroci per tracciare un grafo bipartito completo con 3 e n nodi sul toro è Numero minimo di incroci per un grafo bipartito completo con 3 e n nodi sul toro (Richard K. Guy e T. Jenkyns, 1969).

  • il numero minimo di incroci per tracciare un grafo bipartito completo con 4 e n nodi sul piano proiettivo è Numero minimo di incroci per un grafo bipartito completo con 4 e n nodi sul piano proiettivo (P.T. Ho, 2005);

 

Il problema del minimo numero di incroci in un grafo bipartito completo è anche noto come “problema della fabbrica di mattoni”, perché nel 1977 Turán ne diede una brillante descrizione: “Lavoravamo in una fabbrica di mattoni vicino a Budapest. I mattoni venivano prodotti in alcuni forni e portati in alcuni depositi all’aperto. Tutti i forni erano connessi a tutte le aree di deposito da rotaie e il trasporto avveniva tramite piccoli carrelli spinti a mano. Quello che dovevamo fare era caricare i mattoni ai forni, spingere i carrelli sino ai depositi e scaricarli. Il carico di ogni carrello era ragionevole e il lavoro facile; i problemi avvenivano agli incroci, dove i carrelli avevano la tendenza a deragliare, rovesciando i mattoni e causando problemi e perdite di tempo. In tali occasioni sudavamo e imprecavamo, così mi venne l’idea che le perdite di tempo sarebbero state ridotte minimizzando il numero di incroci. Ma qual è il minimo numero di incroci? Dopo parecchi giorni mi accorsi che in quel caso si poteva migliorare la situazione, ma la soluzione del problema generale con n forni e m depositi sembrava molto difficile.”

 

Recentemente il problema del minimo numero di incroci necessari per tracciare grafi arbitrari ha attratto molto l’interesse, per le connessioni col problema di ridurre il numero di incroci nei circuiti elettronici.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.