Contando el número de supergraphs conectados un mínimo de un dígrafo desconectado arbitraria

Question

Para empezar por "conectado" en el contexto de gráficos, más formalmente, me refiero a "débilmente conectados", además de por la "mínima" estoy usando el término con respecto a la subgrafo relación. Con eso dicho por cualquier desconectado dígrafo $G=(V,E)$ se encuentra siempre conectado dígrafo $H=(V,E')$ sobre el mismo conjunto de vértices $V$$E\subseteq E'$, de modo que $H\supseteq G$ está conectado a un supergraph de $G$ esto se puede hacer mediante la adición de los arcos a $G$ que se conectan todos sus componentes conectados para formar la nueva forma de grafo dirigido $H$ Por ejemplo, uno puede visualizar este proceso por mi toscamente dibujadas diagrama dibujado en microsoft paint:

      

Sin embargo, el dígrafo $H$ se muestra arriba no es mínima con respecto a la subgrafo relación, porque yo podría haber añadido menos flechas para formar otro conectado dígrafo $H'$ satisfacción $G\subseteq H'\subset H$, en particular, me podría quitar una de las dos flechas que conectan dos de los componentes en $H$ conseguir $H'$.

Ahora quiero contar el número de mínimos, conectado, supergraphs de cualquier dissconected gráfico de $G$. O más formalmente, si por cualquier dissconected gráfico de $G$ uno define un conjunto $Q$ como sigue:

$$Q=\small \{D\supseteq G:\left(D\text{ is weakly connected}\right)\land \left(\text{For any digraph }H\text{ we have }G\subseteq H\subseteq D\implies H=D\right)\}$$

A continuación, quiero encontrar el valor de $|Q|$, ahora esta shoudn no ser duro y creo que sé la respuesta. Sin embargo, estoy seguro de si he cometido un pequeño error en mi razonamiento. Creo $|Q|=2^{|S|-1}|S|!\prod_{C\in S}|\mathcal{V}(C)|$

Donde $S$ es el conjunto de componentes conectados en $G$. Mi razonamiento era, básicamente, en primer lugar, si la dividimos el conjunto de $V=\mathcal{V}(G)$ en la familia $\mathcal{F}=\{\mathcal{V}(C):C\in S\}$, ahora bien, si tomamos cualquier conjunto de los distintos representantes de $\mathcal{F}$ podemos formar un camino de $P$ de la longitud de la $|S|-1$ conectando juntos por $|S|-1$ flechas, donde la gráfica de $G\cup P$ debería ser de un mínimo de, conectado supergraph como claramente vemos la $G\subseteq G\cup P$ y la eliminación de cualquiera de las flechas de $P$ debe bajar $G\cup P$ con el que dijo que hay exactamente $\prod_{C\in S}|\mathcal{V}(C)|$ distintos operadores al que podemos elegir desde donde cada uno debe formar un camino diferente $P$, por otro lado, cuando la construcción de cualquier ruta de acceso tenemos a la orden de los vértices y desde allí se $|S|$ será $|S|!$ diferentes ordenamientos, por último, como cada ruta se dirige y por el intercambio de la dirección de las flechas en cualquiera de los caminos que este se $G\cup P$ conectado así porque hay $|P|=|S|-1$ arcos en nuestro camino dígrafo $P$ vemos que el número de los bigramas formado por el intercambio de la dirección de cada arco es $2^{|S|-1}$ por lo que no debería ser exactamente $2^{|S|-1}|S|!\prod_{C\in S}|\mathcal{V}(C)|$ diferentes mínimamente conectado supergraphs de $G$. O, equivalentemente,$|Q|=2^{|S|-1}|S|!\prod_{C\in S}|\mathcal{V}(C)|$. Así es esto correcto? O tengo algún error en mi razonamiento? Cualquier ayuda/correcciones etc. sería apreciada.

Answer 1

Si he entendido su enfoque correctamente, le falta un lugar de gran parte de los casos, es decir, estas, donde las nuevas conexiones forman un árbol en lugar de sólo un camino. Para simplificar el problema, le sugerimos lo siguiente:

1. Crear un multigraph $\mathcal{G}$ de manera tal que sus vértices corresponden a los (débilmente) conectados a los componentes de su gráfica.
2. Entre cualquier par $(v_1, v_2)$ de vértices $\mathcal{G}$ añadir la etiqueta de los bordes, donde las etiquetas se $S_1 \times S_2$ donde $S_i$ es el conjunto de vértices que representan el componente conectado de $G$ correspondiente al vértice $v_i$ (y la dirección inversa será tratada cuando la adición de bordes para el par $(v_2, v_1)$).
3. Contar el número de árboles de expansión en este multigraph con etiquetas de los bordes.

Si su gráfica original $G$ $k$ de los componentes conectados, este enfoque le da la siguiente fórmula:

$$\sum_{T \in \mathcal{T}_k}\ \ \prod_{\{i,j\} \in T, i < j}2\cdot|S_i|\cdot |S_j| = 2^{k-1}\sum_{T \in \mathcal{T}_k}\ \ \prod_{\{i,j\} \in T, i < j}|S_i|\cdot |S_j|$$ donde $\mathcal{T}_k$ es el conjunto de grafo etiquetado de los árboles en $k$ vértices (la última igualdad proviene del hecho de que usted siempre tiene $k-1$ bordes, y cada uno de estos puede estar en una de dos direcciones).

Espero que esto ayude a $\ddot\smile$