Problema sobre la existencia de un ciclo de Bruijn.

Question

Problema sobre la existencia de un ciclo de Bruijn.

inducción
Matemáticas
Teoría de grafos
combinatoria
Matemáticas discretas

Alumno

He logrado probar las partes (a) y (b). Sin embargo, estoy enfrentando dificultades para probar la parte (c). Intenté usar la inducción matemática y primero mostré que la secuencia para $n=1$ $b_1,b_2=(0,1)$ es un ciclo de Bruijn. Entonces supuse que por $k>1$ la secuencia $b_1,b_2,...,b_{2^k}$ es un ciclo de Bruijn. Sin embargo, cuando me resulta difícil mostrar que la secuencia $b_1,b_2,...,b_{2^{k+1}}$ también será un ciclo de Bruijn utilizando el hecho de que $b_1,b_2,...,b_{2^k}$ es un ciclo de Bruijn. Cualquier ayuda será muy apreciada.

Editar: Este problema es del Capítulo $13$ del libro Introducción a la Combinatoria de Richard A Brualdi.

bof

¿Por qué está tratando de usar la inducción para la parte (c)? ¿Por qué no usas el hecho de que tienes un circuito euleriano dirigido?

Alumno

@bof He hecho la edición. ¿La información proporcionada por mí es suficiente?

Alumno

@bof No entiendo completamente tu primer comentario.

Darij Grinberg

En la solución del Ejercicio 3 del conjunto de tareas 2 de mi clase de Matemáticas 5707 Primavera 2017 en la UMN se dan varios detalles más sobre esa prueba . Dicho esto, todavía quedan algunas cosas para el lector. (Uso un multidígrafo en lugar de un dígrafo, para hacer el

n = 1

$n=1$ el caso funciona correctamente; pero para

n > 1

$n>1$ esto no hace ninguna diferencia.)

Alumno

@darijgrinberg gracias por compartir el pdf!

Ewan Delanoy

@ShreyAryan ¿Podría aclarar por qué está poniendo una recompensa en la parte (c) del problema? El pdf de Darij Grinberg lo dice todo (está en las páginas 8-9 del pdf). Qué más necesitas ?

Respuestas (1)

Problema sobre la existencia de un ciclo de Bruijn.

¿Por qué está tratando de usar la inducción para la parte (c)? ¿Por qué no usas el hecho de que tienes un circuito euleriano dirigido?
@bof He hecho la edición. ¿La información proporcionada por mí es suficiente?
En la solución del Ejercicio 3 del conjunto de tareas 2 de mi clase de Matemáticas 5707 Primavera 2017 en la UMN se dan varios detalles más sobre esa prueba . Dicho esto, todavía quedan algunas cosas para el lector. (Uso un multidígrafo en lugar de un dígrafo, para hacer el $n=1$ el caso funciona correctamente; pero para $n>1$ esto no hace ninguna diferencia.)
@ShreyAryan ¿Podría aclarar por qué está poniendo una recompensa en la parte (c) del problema? El pdf de Darij Grinberg lo dice todo (está en las páginas 8-9 del pdf). Qué más necesitas ?

Este sitio se ha convertido en un vertedero. · Answer 1

AYUDA: Cualquier secuencia binaria de longitud $n$ tiene un arco $b_k$ saliendo de eso. Demostrar que la sucesión es igual a $b_k$ , $b_{k+1}$ , ..., $b_{k+n-1}$ .

Problema sobre la existencia de un ciclo de Bruijn.

Alumno

bof

Alumno

Alumno

Darij Grinberg

Alumno

Ewan Delanoy

Respuestas (1)

Este sitio se ha convertido en un vertedero.

Un gráfico máximo conectado GGG sin ciclos de longitud de al menos k+1k+1k+1 tiene |V(G)|≤k|V(G)|≤k|V(G)| \leq k o tiene un vértice cortado cuando k≥2k≥2k \geq 2

Pregunta sobre una prueba de "El gráfico GGG no tiene ciclos impares ⟹⟹\implica que GGG es bipartito"

probar que para n≥2n≥2n \geq 2 no existe un grafo simple de n-vértices cuyos vértices tengan grados distintos

Para cada n≥2n≥2n \geq 2 existe un grafo simple de n-vértices cuyos vértices tienen grados distintos

Número máximo de ciclos de expansión sin borde común en un gráfico completo

Varias pruebas relacionadas con las definiciones de árboles y bosques.

¿Por qué el problema del vendedor ambulante es "difícil"?

Definición de gráfico bipartito del libro de Murty-Bondy

Ayuda de inducción... número de ciudades

Número de rutas óptimas a través de una cuadrícula con una restricción de ruta ordenada