Llegar a todos los posibles gráficos dirigidos simple con una secuencia de grados dado con swaps 2-borde

Question

Comenzando con un simple, en forma de Grafo dirigido G, I definir un dos-borde de intercambio como:

1. seleccione dos bordes u->v y x->a tal que (u!=x) y (v!=y) y (u!=y) y (x!=v)
2. eliminar los dos bordes u->v y x->y
3. agregar bordes u->y y x->v

Se garantiza que puedo llegar a cualquier simple grafo dirigido con el original (dentro y fuera) grado de secuencia en algún número finito de 2 de borde de swaps?

Si necesitamos algún tipo de 3 de borde de swaps, ¿cuáles son?

Antecedentes: tengo la intención de utilizar este como MCMC pasos para la muestra de grafos aleatorios, pero en el Networkx sitio del Desarrollador, hay una discusión que el Teorema 7 del documento P Erdos et al., "Una simple Havel–Hakimi tipo de algoritmo para darse cuenta de gráfica de grado secuencias de gráficos", la Combinatoria de 2010 implica que necesitamos 3-borde de swaps de para disfrutar de todo el espacio.

Answer 1

En la página 6 del documento vinculado, se define un intercambio de triples. Básicamente, se transforma los $v_n \rightarrow v_k \rightarrow v_i \rightarrow v_m$ $v_n \rightarrow v_i \rightarrow v_k \rightarrow v_m$.

Answer 2

La pregunta es si un triple de intercambio es necesario o no. Uno de los ejemplos en el papel es el indicado alternar entre los tres nodos (i>j), (j>k), (k->i). Obviamente, otro gráfico con el mismo grado de secuencia es aquel en el que todas las direcciones son a la inversa: (i < j), (j < k), (k <- i). Es, sin embargo, no es posible obtener a partir de la primera a la segunda gráfica si no permiten el auto-loops: no hay dos bordes cuya swap es permitido bajo esta condición. Al principio pensé que no puede ser un ejemplo de esto es en las grandes gráficos, pero en realidad hay gráficos de tamaño infinito con el mismo problema (bajo la condición de no varias aristas y auto-bucles): de nuevo, empezar con la orientación del triángulo; agregar cualquier número de nodos que están conectados a todos los demás nodos de la bi-direccional de los bordes. Por lo tanto, la única bordes que son flexibles son los que están en el triángulo y de nuevo, todos sus bordes se puede revertir el resultado en un gráfico con el mismo grado de secuencias, pero no de la secuencia de borde-los swaps se puede lograr.

Es obvio que la familia de gráficas en las que se describe aquí es muy limitado, pero puede haber otros con problemas similares. Por lo tanto: hay gráficos que necesita el triple de intercambio s.t. todos los gráficos con el mismo grado de secuencias, pero sin múltiples aristas y auto-bucles de muestras u.una.r.