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

Fabbrica di mattoni (problema della)

Matematica combinatoria  Problemi  Teoria dei grafi 

Il problema della fabbrica di mattoni è il problema del minimo numero di incroci necessari per tracciare sul piano un grafo bipartito completo. In altri termini, il problema consiste nel determinare, dati due insiemi di punti e volendo collegare con una linea (non necessariamente retta) ogni punto di un insieme a tutti quelli dell’altro, quale sia il minimo numero di incroci necessari.

Il termine si deve a Turán, che descrisse una fabbrica di mattoni, con vari punti e vari depositi, collegati da un intreccio di binari sui quali venivano spinti carrelli con i mattoni appena cotti. Notando la tendenza dei vagoncini a deragliare negli incroci, il matematico ungherese si chiese quale fosse il minimo numero di incroci inevitabili nella piccola rete e originò così un problema combinatorio, tuttora irrisolto.

 

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 tra gli archi.

Zarankiewicz dimostrò nel 1954 che la formula rappresenta un limite superiore. La congettura è stata dimostrata per tutti i valori di n e m non superiori a 7 e in vari casi particolari.

 

Le varianti per grafi arbitrari sono state molto studiate in tempi recenti, per le connessioni col problema di ridurre il numero di incroci nei circuiti elettronici.

Vedi anche

Numero di incroci.

Contattami

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