# What is the minimum cost graph inside a strongly connected component, which connects every vertex?

So for MST there are 2 possible definitions in an undirected graph. Keep in mind that in an undirected graph the MST algorithm always has n - 1 edges and no cycles. In an undirected graph, it doesn't matter which definition you use, since both are correct, however inside a directed graph thats not the case anymore. Definitions:

1. Choosing a root vertex u in a graph, the MST is the smallest cost tree which connects every other vertex from u.
2. Given a graph, the minimal cost subgraph which connects all nodes is called a MST. (In an undirected graph this must be a tree)

In a directed graph the first definition for a directed graph is arborescence. However the arborescence is different with every vertex you choose (This is not the case in an undirected graph), resulting in multiple possible directed MST variations. In the links section i have a video which explains the def. of an arborescence.

The second definition requires the directed graph to be one big strongly connected component. Hence it is now possible to go from any vertex u to any other vertex v, there is only 1 MST in a directed graph. However now we are not talking about trees anymore, hence the MST must include cycles. In the links section i included a graph as example for the second definition. In this image there are more then 1 possible minimum graphs, one for either of the red edges removed for example.

My question is, what is second definition called in a directed graph? (Does it have a special name like arborescence) and if so, isn't that the directed variant of MST? Is there an algorithm to compute the minimum graph inside a strongly connected component?

Definition of arborescence on Wikipedia

Quick video explaining what an arborescence is

I created a graph example of what i mean with the second definition: • Yet another vocabulary lesson. Jan 2, 2015 at 17:43
• The language barrier really is hard sometimes, isn't it. My question simply put is: What is the minimum cost graph inside a strongly connected component, which connects every vertex with every other vertex.
– bvoq
Jan 2, 2015 at 17:44