grafos:brickfactory [WikiMat]

===== O Problema da Fábrica de Tijolos =====

Durante a Segunda Guerra Mundial, o matemático húngaro **Pál Turán** foi forçado a trabalhar em uma fábrica de tijolos, empurrando vagões sobre trilhos que ligavam os fornos aos armazéns da fábrica. Turán observou que os vagões eram mais difíceis de empurrar em pontos onde os trilhos se cruzavam e, inspirado por essa situação, começou a se perguntar como a fábrica poderia ser rearranjada a fim de minimizar o número de tais cruzamentos.

É fácil ver que o esquema geral da fábrica pode ser representado por um grafo [[grafos:defbipartite|bipartido completo]] em que os vértices estão particionados em fornos e armazéns. No entanto, para traduzir os cruzamentos de trilhos para a linguagem de Teoria dos Grafos, precisamos de mais alguns conceitos.

<WRAP info round box 80%>
=== Imersão ===
Uma **imersão do grafo no plano** é uma representação dele no plano em que pontos representam vértices e arcos ligando pares de pontos que se relacionam representam arestas.
</WRAP>

<WRAP tip round box 80%>
Em geral, pode-se entender a imersão de um grafo no plano como uma forma (note que podem haver várias) de desenhá-lo em uma folha de papel.
</WRAP>

Nem sempre é possível evitar que os arcos de uma imersão se cruzem, o que pode causar confusão na interpretação do grafo que ela representa. Em geral, quanto menos cruzamentos ocorrerem, mais claro é o desenho. Essa questão motiva a seguinte definição:

<WRAP info round box 80%>
=== Número de cruzamentos ===
O **número de cruzamentos** de um grafo $G$, denotado por $cr(G)$, é o menor número possível de interseções entre os arcos de uma imersão de $G$ no plano.
</WRAP>

<WRAP round box 80%>
=== Problema da Fábrica de Tijolos ===
Dados $m, n$ inteiros positivos, qual o valor de $cr($[[grafos:defbipartite|$K_{m,n}$]]$)$?
</WRAP>

<WRAP tip round box 80%>
Como $K_{m,n}\simeq K_{n,m}$, podemos supor, sem perda de generalidade, $m\ge n$.
</WRAP>

Se, por exemplo, $n\le 2$, então $cr(K_{m, n})=0$, como sugere a imagem a seguir.

{{ :grafos:km1_e_km2.png?600 |}}

Após o fim da guerra, em 1952, Turán apresentou o problema em algumas palestras na Polônia e alcançou, em ocasiões diferentes, os matemáticos **Kazimierz Urbanik** e **Kazimierz Zarankiewicz**. Três anos mais tarde, os dois publicaram, de forma independente, artigos sugerindo soluções equivalentes para o problema. Infelizmente, ambas as soluções estavam incorretas. No entanto, nenhum contraexemplo para a fórmula apresentada, conhecida como **Conjectura de Zarankiewicz**, foi encontrado até o presente momento.

<WRAP round box 80%>
=== Conjectura de Zarankiewicz ===
$cr(K_{m, n}) = \bigg\lfloor\dfrac{m}{2}\bigg\rfloor\bigg\lfloor\dfrac{m-1}{2}\bigg\rfloor\bigg\lfloor\dfrac{n}{2}\bigg\rfloor\bigg\lfloor\dfrac{n-1}{2}\bigg\rfloor$.
</WRAP>

A imersão que atinge esse número de cruzamentos é obtida da seguinte forma: 

Sejam $A = \{a_1, \dots, a_m\}$ e $B = \{b_1, \dots, b_n\}$ os conjuntos da bipartição de $G\simeq K_{m, n}$; posicione os vértices de $A$ com índice ímpar sobre o eixo-$x$ positivo e os com índice par sobre o eixo-$x$ negativo, e faça o mesmo com os vértices de $B$ substituindo o eixo-$x$ pelo eixo-$y$. A imagem a seguir mostra uma tal imersão para $m = 6, n = 5$.

{{ :grafos:grafo_de_zarankiewicz.png?600 |}}

<WRAP tip round box 80%>
O fato de existir uma imersão com esse número de cruzamentos mostra que $cr(K_{m, n}) \le \bigg\lfloor\dfrac{m}{2}\bigg\rfloor\bigg\lfloor\dfrac{m-1}{2}\bigg\rfloor\bigg\lfloor\dfrac{n}{2}\bigg\rfloor\bigg\lfloor\dfrac{n-1}{2}\bigg\rfloor$. Assim, para demonstrar a conjectura, basta mostrar que $cr(K_{m, n}) \ge \bigg\lfloor\dfrac{m}{2}\bigg\rfloor\bigg\lfloor\dfrac{m-1}{2}\bigg\rfloor\bigg\lfloor\dfrac{n}{2}\bigg\rfloor\bigg\lfloor\dfrac{n-1}{2}\bigg\rfloor$.
</WRAP>

A solução de Zarankiewicz, apesar de conter um erro, foi capaz de demonstrar corretamente o [[grafos:brickfactory:caso_n=3|caso $n=3$]].

<WRAP round tip 80%>
=== Curiosidades ===
  * A Conjectura de Zarankiewicz é verdadeira para $n\le 6$ e $n=7, m\le 9$, ou seja, o menor caso em aberto é o $K_{9,9}$.
  * [[grafos:brickfactory:menor_contraexemplo|O menor contraexemplo para a conjectura (se existir) deve ter $m, n$ ímpares.]]
  * Já se mostrou que, para grafos suficientemente grandes, a solução do problema deve ser pelo menos $83\%$ do número de Zarankiewicz.
  * Restringindo os arcos da imersão à segmentos de reta, o Problema da Fábrica de Tijolos ainda é um problema em aberto.
  * Determinar o número de cruzamentos de um grafo [[grafos:defcompleto|completo]] também é um problema em aberto.
</WRAP>

<WRAP round info 80%>
=== Referências ===
  * Lowell Beineke e Robin Wilson. [[https://link.springer.com/article/10.1007/s00283-009-9120-4|“The Early History of the Brick Factory Problem”.]] Em: The Mathematical Intelligencer 32 (2010), pp. 41–48.
  * S. W. Bowen. [[https://www.cantorsparadise.com/tur%5C%C3%5C%A1ns-brick-factory-problem-c07ac4f1a54f|Turán’s Brick Factory Problem.]] 2022.
  * Richard K. Guy. “The decline and fall of Zarankiewicz’s theorem”. Em: Proof Techniques in Graph Theory (1968), pp. 63–69.
  * Kazimierz Zarankiewicz. “On a problem of P. Turan concerning graphs”. Em: Fundamenta Mathematicae 41 (1955), pp. 137–145.
</WRAP>