Dado un gráfico $G$ de $N$ nodos y $E$ aristas, construimos un nuevo gráfico $G^{'}$ con $N^2$ nodos de tipo $(a,b)$ . Hay una ventaja entre $(a,b)$ y $(a^{'},b^{'})$ en $G'$ si tenemos una arista de $a$ a $a^{'}$ y $b$ a $b^{'}$ en $G$ .
Necesitamos encontrar el número de componentes conectados en $G'$ .
Mi trabajo:
Podemos eliminar los vértices aislados contando su contribución a la respuesta, que sería $N^2-(N-isolated)^2$ .
Ahora, no sé cómo avanzar pero la respuesta se basa en el número de componentes bipartitos y no bipartitos en $G$ que no soy capaz de pensar.
Respuesta
¿Demasiados anuncios?
Finalmente entendí cómo no de componentes bipartitos(digamos, $bip$ ) y otros componentes(digamos, $oth$ ) entran en escena.
Considere un nodo $(b1,b2)$ en $G'$ . Aquí $b1,b2$ represenet nodos de 2 componentes bipartitos de $G$ . Es hermoso observar que todos los $(white,white)$ y $(black,black)$ nodos forman 1 componente conectado, y todos $(white,black)$ y $(black,white)$ forman otro componente conectado en $G'$ . Por lo tanto, obtenemos el total $2*bip^2$ componentes en $G'$ .
Consideremos un nodo de tipo $(bipartite,other)$ o $(other,bipartite)$ en $G'$ . Ahora, los nodos formados por su producto forman un único componente conectado en $G'$ . Así que obtenemos su contribución como $2*bip*oth$ .
Por último, considere el nodo de tipo $(other,other)$ . Su contribución será $oth*oth$ por motivos similares.
Así que la respuesta final es $N^2-(N-isolated)^2+2bip^2+2.bip.oth+oth^2$
