17 votos

En la teoría de los gráficos, ¿cuál es la diferencia entre un "sendero" y un "sendero"?

Estoy leyendo la Combinatoria y Teoría de grafos, 2ª Ed., y estoy empezando a pensar que los términos utilizados en el libro podría ser obsoleta. Revise el siguiente pasaje:

Si los vértices de un pie son distintos, entonces el pie se llama una ruta de acceso. Si los bordes en una caminata son distintos, entonces el pie se llama una pista. De esta manera, cada camino es un camino, pero no todo el camino es un camino. ¿Lo tienes?

Por otro lado, la Wikipedia del glosario de teoría de grafos términos define senderos y caminos de la siguiente manera:

Un camino es un paseo en el que todos los bordes son distintos. Cerrado sendero ha sido llamado un tour o circuito, pero estos no son universales, y el último es a menudo reservado para un subgrafo de grado dos.

Tradicionalmente, un camino que se refiere a lo que ahora se conoce generalmente como un proceso abierto a pie. Hoy en día, cuando afirma sin ninguna cualificación, un camino que se entiende generalmente para ser simple, lo que significa que no hay vértices (y por lo tanto no hay bordes) se repiten.

¿Debo entender que la Combinatoria y Teoría de grafos, 2ª Ed. es el uso de un desactualizados definición de la ruta, en referencia a lo que ahora se conoce como un abrir de a pie? ¿Cuáles son los canónica de las definiciones de los términos "caminar", "camino", y "camino"?

13voto

DiGi Puntos 1925

Usted parece haber entendido mal algo, probablemente las definiciones en el libro: son realmente los mismos que las definiciones que Wikipedia describe como las actuales.

1voto

mcflause Puntos 118

Un paseo de longitud k es una secuencia alterna no vacía de vértices y aristas en G.

Un paseo es un sendero si algún borde se atraviesa a lo sumo una vez.

Un rastro es un camino si cualquier vértice se visita como máximo una vez, excepto posiblemente los vértices inicial y terminal cuando son iguales.

0voto

Dutta Puntos 3026

Hoy también me he enfrentado al mismo problema para leer estos primeros conceptos. Mi entendimiento es como sigue.

Ruta: Un camino es un grafo simple cuyos vértices pueden ser ordenados de manera que dos vértices sean adjuntos si son constitutivos en la lista.

Walk: es una lista de vértices y aristas$v_0, e_1, v_1, \dots, e_k, v_k$ para$1\le i \le k$,$e_i$ tiene un punto final$v_{i-1}, v_i$.

Juicio: Es un paseo sin margen repetido.

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