Matematicas con grafos

Soltrac

Alguien q me recuerde la demostración de porque este problema no tiene solución?

http://www.supuzzle.com/

Gracias :)

PD: Si alguien piensa que tiene solución, que lo intente hacer.

4rafa4

oues parece xungo

Pero todos sabemos que la acometida de la luz ha de ir por encima de la del agua asi que srry es una xorrada

squ4r3

es imposible.

porque yo lo he intentado y no me sale xD

NeSSi

creo que tenia que ver con la planaridad de un grafo.

edito:
En teoría de grafos, un grafo planar es un grafo que puede ser dibujado (los matemáticos se refieren más formalmente como "embebido" en un plano) sin que ninguna arista se interesecte

En la práctica, es difícil usar el teorema de Kuratowski para decidir rápidamente si un grafo es planar. Sin embargo existe un algoritmo rápido para este problema: para un grafo de n vértices y e el número de aristas, es posible determinar en tiempo O(n) (lineal) si el grafo es planar o no.

Teorema 1. Si n ≥ 3 entonces e ≤ 3n - 6
Teorema 2. Si n > 3 y no existen ciclos de longitud 3, entonces e ≤ 2n - 4 

http://es.wikipedia.org/wiki/Grafo_planar

Spachu_4Ever

La ultima linea que falta no se puede poner porque las demas envuelven la casa

J

Si en un grafo en más de dos puntos confluyen un número impar de líneas no tiene solución ;) Sólo puede haber dos puntos con confluencia impar, que son los puntos que se usarán para comenzar y para terminar. (Evidentemente este no se puede, porque los tres necesitan tres líneas respectivamente).

L

aki esta como se resuelve en un video http://uncutvideo.latino.aol.com/videos/8b651af945c20d4554c898fab0d3ba0d

PD:a mi me salio xD

Posteador11

Es un K3,3, ningún grafo Kn,n con n>2 es plano.

El de #7 usa chetos.

Pansman

Doy gracias al señor por haber olvidado todo lo que aprendí en mis dos años de telecos.

RoBErTiTo

omg

Thanat0s

Jeje, todos los que hemos estudiado grafos fijo que por fin hemos pensado que sirve para algo xD

K

joder he estao un buen rato intentandolo y nada xD

P

pues a mi me ha salido:

http://img509.imageshack.us/img509/8758/iwinxx1.jpg

no lo intenteis si no sabeis darle al boton derecho.

PLeaSuReMaN

lo que dice #8

los kn,n no cumplen el teorema de euler

pd: #11

AlKhwarizmi

Hay varias maneras de demostrar que no existe solución a eso. Creo recordar que la más sencilla es utilizando la fórmula de Euler que se da en todos los grafos planos (y que también sirve para poliedros):

Caras + Vértices = Aristas + 2.

Por construcción, la solución del problema tiene que tener 6 vértices (las casas y los servicios) y 9 aristas (las conexiones de cada casa a los tres servicios). Por lo tanto, por esa fórmula (que habría que demostrar también, claro) tendría que tener 9 caras.

Sin embargo, por otra parte, podemos ver que cada cara de la solución ha de tener al menos 4 aristas, ya que tiene que ser de la forma casa -> servicio -> casa -> servicio o bien casa -> servicio -> casa -> servicio -> casa -> servicio (unir dos casas o dos servicios entre sí no tiene sentido).

Si cada cara tiene al menos cuatro aristas, el número de aristas de la solución es al menos (5*4)/2 = 10. (cinco caras, cuatro caras por arista, y cada arista se está contando dos veces, de ahí la división).

Esto contradice la fórmula de Euler. Ergo, la solución no puede existir.

Q.E.D. :)

Soltrac

Tiene sentido lo q decis. Muchas gracias!!!!

Usuarios habituales

  • Soltrac
  • Thanat0s
  • RoBErTiTo
  • Pansman
  • Lineage
  • Spachu_4Ever
  • squ4r3