Un grafo dirigido ponderado es una forma razonable de expresar la entrada del problema, pero eso en sí mismo no nos dice mucho sobre qué hacer con ese gráfico.
Intentemos resolver una variante básica:
Dado un gráfico de fracciones de propiedad entre empresas, si poseo una $p$ % de participación en la empresa $A$ lo grande que es un total participación de la corporación $B$ ¿me da eso? Aquí, "total" significa "indirecto" si $B\ne A$ y "directo más indirecta" cuando $B=A$ .
Debe quedar claro que la respuesta debe ser proporcional a $p$ Así que escribamos la respuesta como $\frac{p}{100}x_{AB}$ , donde $x_{AB}$ es un coeficiente desconocido que intentaremos calcular.
Vamos a escribir $g_{AB}$ para "la fracción de $B$ de las acciones de la sociedad anónima $A$ ". Estos coeficientes son entradas conocidas para el problema (puede reconocerlos como los elementos de la matriz de incidencia para el gráfico de propiedad). Además, para definir el ejemplo, supondremos que sólo hay 3 empresas, $A$ , $B$ y $C$ en el mundo. Debería estar claro cómo generalizar a gráficos más grandes.
Ahora, poseer una acción si $A$ es (a efectos del problema simplificado, si no en la realidad económica) equivalente a poseer esa fracción de $A$ de otras empresas (o de ella misma): $$ x_{AB} = g_{AA}x_{AB} + g_{AB}x_{BB} + g_{AC}x_{CB} $$ Vemos que investigar $x_{AB}$ nos lleva a considerar $x_{BB}$ y $x_{CB}$ Así que vamos a escribir las ecuaciones correspondientes para ellos: $$ x_{BB} = g_{BA}x_{AB} + g_{BB}x_{BB} + g_{BC}x_{CB} + 1 $$ $$ x_{CB} = g_{CA}x_{AB} + g_{CB}x_{BB} + g_{CC}x_{CB} $$ El final $1$ en la ecuación de $x_{BB}$ representa el directo propiedad de $B$ obtenemos al poseer $B$ acciones.
Lo que tenemos ahora es un sistema de ecuaciones lineales en tres incógnitas. Tales sistemas son el dominio de álgebra lineal y tienen métodos estándar de solución. El que se enseña en la introducción al álgebra lineal es Eliminación gaussiana En este caso, existen varios refinamientos para las implementaciones informáticas que pretenden reducir la pérdida de precisión que conlleva la aritmética de punto flotante. Para este problema en particular, es probable que la mayoría de las empresas no posean acciones de otras empresas, por lo que nuestro sistema de ecuaciones es escaso y hay algoritmos especiales optimizados para ese caso.
Es posible que un sistema de ecuaciones lineales no tenga soluciones o tenga múltiples soluciones. El caso de no-solución no debería surgir aquí, siempre que la entrada no sea una locura (es decir, no hay fracciones de propiedad negativas, y la fracción total de cada corporación propiedad de otras corporaciones no puede exceder el 100%). El caso de solución múltiple se dará si hay un grupo de empresas que se poseen mutuamente al 100% sin ningún propietario externo, pero es fácil reconocer de antemano estos grupos de autopropietarios y excluirlos del cálculo mediante algoritmos de grafos estándar (sólo se consideran las empresas que son accesibles en el grafo desde algún propietario humano conocido).
En resumen, resultó que para encontrar la cantidad de $B$ una participación en $A$ implica, naturalmente también encontramos respuestas a cuánto de $B$ que se obtiene de una acción en cualquier corporación. Así que si todo lo que eventualmente te interesa son los activos no accionarios de $B$ se puede hacer el cálculo una vez y multiplicar el $x_{\_B}$ s por su cartera.
Por otro lado, si lo que le interesa no es "quién es dueño de cuánto de $B$ ?", sino "¿cuánto de todo poseo?", la estrategia anterior requeriría que hicieras todo el cálculo con ecuaciones ligeramente diferentes para cada empresa. En ese caso, sería mejor utilizar un conjunto diferente de ecuaciones con variables $y_A$ , $y_B$ y $y_C$ representando el total fracciones de cada empresa que posee, y las ecuaciones:
$$\begin{align}y_A &= g_{AA}y_A + g_{AB}y_B + g_{AC}y_C + \tfrac{p_A}{100}\\ y_B &= g_{BA}y_A + g_{BB}y_B + g_{BC}y_C + \tfrac{p_B}{100}\\ y_C &= g_{CA}y_A + g_{CB}y_B + g_{CC}y_C + \tfrac{p_C}{100}\end{align}$$ donde $p_A$ es el porcentaje de $A$ que posee directamente, etc.
El resultado de este cómputo alternativo es el mismo que el que se obtiene utilizando el $x_{PQ}$ s, lo que puede verse con un poco de álgebra lineal adicional. Resulta que el $x_{PQ}$ incógnitas resultan ser los elementos de la matriz inversa de $I-(g_{ij})$ . Esto da una relación entre los resultados del primer y segundo método, digamos, $$ y_B = x_{AB}\tfrac{p_A}{100} + x_{BB}\tfrac{p_B}{100} + x_{CB}\tfrac{p_C}{100} $$
Así que para conseguir todo respuestas en un solo cálculo, se podría invertir $I-(g_{ij})$ de una vez por todas; también hay métodos estándar para ello. Sin embargo, la eficacia de este método depende de lo disperso que sea el gráfico de propiedad.
