Verificamos de forma profundamente cada noticia de nuestra página web con el objetivo de enseñarte siempre la información veraz y actualizada.
Solución:
…en un gráfico dirigido, ¿qué lo hace no isomorfo?
Como adjetivo para un gráfico individual, no isomorfo no tiene sentido No se puede hablar con sensatez de que un solo gráfico no sea isomorfo. De lo que podemos hablar es de conjuntos de gráficos que no son isomorfos por parejas (es decir, dos gráficos cualesquiera del conjunto no son isomorfos).
Hablando intuitivamente, dos gráficos $G$ y $G’$ son isomorfos si tienen esencialmente la misma estructura (y no isomorfos en caso contrario). Formalmente, dos grafos son isomorfos si hay una biyección que conserva los bordes desde los vértices de $G$ hasta los vértices de $G’$.
En el siguiente ejemplo, los dos dígrafos rojos tienen esencialmente el mismo dígrafo: hay un nodo con dos bordes exteriores. Una biyección que conserva el borde (es decir, un isomorfismo) en este caso es $1 mapsto 2$, $2 mapsto 1$ y $3 mapsto 3$.
No existe tal biyección entre los dígrafos rojo y azul ya que no tienen las mismas secuencias de grados de entrada/salida.
¿Se incluye un conjunto de vértices todos aislados? (algunas soluciones dicen que sí, pero ¿cómo puede llamarse ‘dirigido’?)
El vértice $n$ null dígrafo (es decir, $n$ vértices y sin bordes) se considera consistentemente como un gráfico dirigido.
¿Cuántos grafos simples dirigidos no isomorfos hay con n vértices, cuando n es 2, 3 o 4?
Para responder a esta pregunta se requiere algo de contabilidad. Los dígrafos del nodo $2$ se enumeran a continuación. Tenga en cuenta que incluyo la posibilidad de bordes bidireccionales (es decir, un borde de $A$ a $B$ y un borde de $B$ a $A$).
El número de dígrafos crece rápidamente y está dado por A000273 de Sloane. Para los dígrafos de nodo $2$, $3$- y $4$, los números son $3$, $16$ y $218$, respectivamente (permitiendo bordes bidireccionales).
Si me presionaran para encontrar estos números, haría que mi computadora los encontrara:
- mantener una lista de dígrafos “encontrados”, y
- generar todas las matrices de adyacencia posibles, y para cada una verificar si es isomorfa a un dígrafo en la lista; si no lo es, agréguelo a la lista, y si no lo es, descarte este dígrafo.
Este sería un método de generación bastante ineficiente, pero sería lo suficientemente rápido para dígrafos de $4$-nodo.
¿Puede haber varios gráficos en la respuesta que tengan el mismo número de aristas y los mismos totales de grados de entrada/salida, o una firma distinta de número de arista y total de grados de entrada/salida constituye un gráfico distinto?
Puede haber, aquí hay un ejemplo:
y uno sin bordes bidireccionales:
En la tabla de la pregunta hay una serie de omisiones (es por eso que lo haría en una computadora).
Ha observado correctamente, por ejemplo, que:
no son isomorfos, ya que los grados de entrada/salida no coinciden. Por la misma razón, por ejemplo:
tampoco son isomorfos. Omisiones similares (donde cambiamos las direcciones de los bordes) ocurren en otros casos.
Tampoco veo 3 ciclos orientados con un vértice aislado.
Nota: A001174 de Sloane afirma que hay 42 dígrafos en 4 vértices.
Acuérdate de que tienes la capacidad de aclarar tu experiencia si encontraste tu preocupación a tiempo.