¿Cómo determinar el número de grafos dirigidos/sin señas?

Question

¿Yo soy tipo de pegado en este problema de tarea, alguien me podria dar un trampolín para él?

Si tenemos $n\in\mathbb{Z}^+$, y dejamos que el conjunto de vértices $V$ un conjunto de tamaño $n$, ¿cómo podemos determinar el número de gráficos/gráficos gráficos dirigidos, portaboquillas con lazos etcetera.? ¿Hay una fórmula para esto? Siento que se puede hacer utilizando combinatoria pero bastante no puedo encontrar la. ¿Alguna idea?

¡Gracias!

Answer 1

Inicio: vamos a mostrar cómo contar etiquetados, loopless, sin gráficos. Hay $\binom{n}{2}$ maneras de elegir un conjunto de $\{u,v\}$ de dos vértices. Para cada conjunto, decimos sí o no dependiendo de si hemos decidido unirse a $u$ $v$ por un borde. Alternativamente, pero algo menos concreto, vamos a $P$ ser el conjunto de todos (desordenada) pares. Este conjunto $P$ tiene cardinalidad $\binom{n}{2}$. Para especificar un loopless grafo no dirigido, se elige un subconjunto de a $P$ y conectar cualquier desordenada de par en ese subconjunto por un borde. Cuántos subconjuntos no $P$?

Para extender a los gráficos con los posibles bucles (pero a más de uno por vértice) es similar sí/no proceso.

Answer 2

Para el etiquetado de los vértices:

Contar grafo loopless los gráficos no repite aristas, primer conde posible de los bordes. Como Andre cuenta, hay $\binom{n}{2}$ dichos bordes. Uno por uno, cada borde se incluye o excluye. Así que esto da $2^{\binom{n}{2}}$ posible gráficas.

Si loopless los gráficos no repite aristas están dirigidas, cada par de vértices $a<b$ brinda $3$ posibilidades de un (potencialmente ausente) del borde. ¿Ve usted lo que son y lo que modifica el conde?

Si hay bucles (pero todavía no repite aristas), entonces cualquiera de los escenarios anteriores son modificados por darse cuenta de que no se $n$ más pares de puntos a considerar - aquellos donde la $a=b$. ¿Puedes ver cómo esto podría modificar el recuento de los gráficos? Tenga cuidado, que en realidad no hacen sentido a contar un bucle como se indica.

Answer 3

Sin algunas restricciones, hay infinitamente muchos, así que sospecho que al menos tengan el supuesto de que usted no puede tener más de una arista entre un par de vértices.

Usted debe pensar acerca de lo que el máximo número posible de aristas, se podría tener es en un gráfico con $n$ vértices (es por eso que debe asumir ningún varias aristas, por lo que el número es finito, pero será diferente dependiendo de si se permiten bucles o no). A continuación, especificar un gráfico en particular en $n$ vértices, es necesario especificar si cada uno de los posibles bordes aparece en el gráfico en particular o no. Si su gráfica debe estar orientada, entonces usted tiene la opción adicional de que forma la arista debe apuntar. A continuación, usted debe ser capaz de ennumerate el número total de posibles opciones (si no se puede, hágamelo saber y voy a añadir más detalles aquí - como esta la etiqueta de la tarea no quiero dar demasiado lejos de inmediato!).