Alguém sabe como provar a impossibilidade de resolver o problema "água,luz e gás"? Grafo planar?

Question

São dadas 3 casas e três fontes: uma de água, uma de luz e uma de gás. Todos estes 6 pontos estão em um plano. Ouvi dizer que a teoria dos grafos planar conseguiria explicar porque é impossivel ligar com linhas cada uma das 3 casas com água, luz e gás sem que as linhas se cruzem. Alguem conhece uma prova sucinta, mas fácil, disto?

Answer 1

Sim, eu conheço. Mas eu não me lembro do link. Eu vou lhe escrever depois. Há uma tutorial sobre teoria de grafos que é muito simples e muito interessante. Eu acho que eu li a prova nesse link

Eu vou tratar de lembrar:
a b c
l \ l/ l
A B C

Eu posso comunicar a com A, b e c usando arcos que vão foira deste gráfico. Mas, quando eu trato de comunicar C com a ou b, isto é impossível porque os arcos se juntam.

OK, vou lhe mandar o link se eu posso o achar.

Tchau

Ana

Answer 2

O erro no raciocínio do prezado consulente está em considerar, em pleno Século XXI, um mero "Grafo Planar", quando, seguramente, já devem existir, tanto modelos norte-americanos, quando europeus, de Grafos Supersônicos ou, mesmo, Grafos a Jato.

Tente rever os conceitos com base nas novas coordenadas fornecidas . . .