5 votos

Fáry ' teorema s para gráficos infinitos

Fáry del teorema es un (bastante conocido) declaración en la que afirma que cada finito simple plano gráfico se pueden extraer de una manera tal que cada arista es representado por un segmento de línea recta.

¿Este teorema se extienden a countably infinito gráficos?

Un estándar de prueba de este teorema se procede por inducción sobre el número de vértices, y por lo tanto es unapplicable aquí. Sospecho que la respuesta es no, pero no puedo pensar de un contraejemplo.

Gracias de antemano.

2voto

Zur Luria Puntos 1000

Parece que este problema fue solucionado. He encontrado un papel demostrando que cada gráfico planar infinita tiene una representación de la línea recta.

http://CiteSeerX.IST.PSU.edu/viewdoc/download?DOI=10.1.1.102.1891&REP=Rep1&type=pdf

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X