Problema de un solo trazo y explicación

El problema de un trazo es un problema famoso en la teoría de grafos. El problema del one-stroke surgió del problema de los siete puentes de Königsberg. En su artículo "Los siete puentes de Königsberg" publicado en 1736, el matemático Euler no sólo resolvió el problema de los siete puentes, sino que también propuso el teorema de un trazo, que por cierto resolvió el problema de un trazo [1]. En general, se cree que la investigación de Euler es el comienzo de la teoría de grafos.

Un problema de teoría de grafos correspondiente al problema de un trazo es el problema hamiltoniano.

Índice[Ocultar]

1 Pregunta planteada

2 Teorema de un golpe

2.1 Teorema 1

2.2 Teorema 2

3 ejemplos

3.1 Problema de los siete puentes

3.2 Un ejemplo de problema de un solo golpe

4 Un- problema del accidente cerebrovascular y problema de Hamid Dayton

5 Ver también

6 Fuentes de referencia

[editar] Pregunta planteada

Un problema del accidente cerebrovascular es el Problema clásico de Königsberg La generalización después de la abstracción es un tipo de problema de recorrido de grafos. En el problema de Königsberg, si el área conectada por el puente se considera como un punto y cada puente se considera una arista, entonces el problema será: para un gráfico conectado G(S, E), ¿podemos encontrar un camino que contenga ¿Exactamente todos los bordes y no tiene duplicados? Euler generalizó este problema a: Para un gráfico conectado dado, ¿cómo determinar si existe un camino que contenga exactamente todos los bordes sin duplicación? Esto es cuestión de un solo golpe. En términos de teoría de grafos, se trata de determinar si el gráfico es un gráfico que puede atravesar todos los bordes sin duplicación. Estos gráficos ahora se denominan gráficos de Euler. El camino recorrido en este momento se llama camino de Euler (un ciclo o una cadena). Si el camino es cerrado (un ciclo), se llama circuito de Euler [1].

La generalización del problema de un trazo es el problema de múltiples trazos, es decir, para una imagen que no se puede dibujar de un solo trazo, explore el número mínimo de trazos que se pueden usar para dibujarlo.

[editar] Teorema del dibujo de un trazo

Para el problema del dibujo de un trazo, existen dos criterios de juicio, los cuales fueron propuestos y demostrados por Euler [1].

[Editar] Teorema 1

Las condiciones necesarias y suficientes para que un grafo finito G sea una cadena o un ciclo son: G es un grafo conexo y el número de vértices impares es igual a 0 o 2. Un grafo G finitamente conexo es un ciclo si y sólo si no tiene vértices singulares [2].

Prueba [2][3]:

Necesidad: Si un gráfico se puede dibujar de un solo trazo, entonces para cada vértice, ya sea el número de aristas que "entran" en este punto en el camino Igual al número de aristas que "salen" del punto: el grado del punto es par. O los dos difieren en uno: entonces este punto debe ser uno de los puntos inicial o final. Tenga en cuenta que si hay un punto inicial, debe haber un punto final, por lo que el número de vértices impares es 0 o 2.

Suficiencia:

Si no hay ningún vértice impar en el gráfico, simplemente elige un punto y conecta un círculo C1. Si este círculo es la imagen original, entonces se acabó. De lo contrario, dado que el gráfico original está conectado, C1 y otras partes del gráfico original deben tener un vértice común s1. A partir de este punto, repita los pasos anteriores para el resto de la imagen original. Dado que la imagen original es finita, después de varios pasos, la imagen completa se divide en algunos círculos. Dado que dos círculos conectados son un círculo, la imagen original también es un círculo.

Si hay dos vértices impares u y v en el gráfico, agregar una arista más para conectarlos dará como resultado un gráfico finito conectado sin vértices impares. Por lo anterior, sabemos que este gráfico es un círculo, por lo que después de eliminar los bordes recién agregados, se convierte en una cadena, con el punto inicial y el punto final siendo u y v.

[Editar] Teorema 2

Si el gráfico finito conectado G tiene 2k vértices impares, entonces se puede dibujar con k trazos, y se debe dibujar con al menos k trazos [ 2].

Prueba [2][3]: divide estos 2k vértices impares en k pares y conéctalos respectivamente, luego obtendrás un gráfico finito conectado sin vértices impares.

De lo anterior, sabemos que este gráfico es un círculo, por lo que después de eliminar los bordes recién agregados, se convertirá como máximo en k cadenas, por lo que debe dibujarse con k trazos. Pero suponiendo que todo el gráfico se puede dividir en q cadenas, entonces, según el teorema 1, solo hay dos vértices impares en cada cadena, por lo que. Por tanto hay que dibujarlo con k trazos.

[editar] Ejemplo

Imagen 1: No se puede dibujar un trazo

Imagen 2: Aunque según los hábitos de escritura chinos, los caracteres de "cadena" son más que de un solo trazo, pero se puede escribir de un solo trazo. [Editar] Problema de los Siete Puentes

La Figura 1 a la derecha es un modelo abstracto del Problema de los Siete Puentes, que consta de cuatro vértices y siete aristas. Tenga en cuenta que los cuatro vértices son impares. Por el teorema 1, sabemos que no se pueden dibujar de un solo trazo.

[editar] Un ejemplo que se puede dibujar de un solo trazo

La Figura 2 es un modelo obtenido después de abstraer la palabra china "cadena". Dado que solo los vértices superior e inferior son impares, sabemos por el teorema 1 que se puede dibujar de un solo trazo.

[editar] Problema de un trazo y problema hamiltoniano

El problema de un trazo analiza si todos los bordes de un gráfico se pueden atravesar sin repetición y si hay vértices o vértices. en él, no hay ningún requisito para repetir pases. El problema hamiltoniano analiza el recorrido de vértices: ¿se pueden atravesar todos los vértices de un gráfico sin repetición? [4] El problema hamiltoniano fue propuesto por primera vez por Hamilton en 1856 y aún no se ha resuelto por completo [2].

[editar] Ver también

Problema de los siete puentes de Königsberg

Problema de Hamilton

Árbol (teoría de grafos)

Problema del cartero de China

[editar] Fuentes de referencia

^ 1.0 1.1 1.2 Janet Heine Barnett, Primeros escritos sobre teoría de grafos: circuitos de Euler y el problema del puente de Köonigsberg

^ 2,0 2,1 2,2 2,3 2,4 Xiong Bin, Zheng Zhongyi, "Graph Theory", Capítulo 4, 38-46, East China Normal University Press.

^ 3.0 3.1 Prueba detallada

^ Diagrama de Euler y diagrama hamiltoniano