Minimum Spanning Trees (MST)

-
Let's imagine an undirected graph with weighted edges.


From this graph, the spanning tree wil be a tree that maps all the vertices. In other words, the tree seen above will be G = (V, E) = (4, 5) and the spanning tree must be at least S = (4, 3). Let us visualize us this down below.


Here we will have S = (4, 3) marked with green, which will be our spanning tree. As we can see, it covers all the vertices in the tree. However, it doesn't cover all the vertices in regards to the weighted edges. This S tree will have the sum of 4 + 5 + 2 = 11.

Now when it comes to minimal spanning trees, we have to care about the weighted edges in the graph. Let's find the minimal spanning tree of the G graph above.

Let's call this subgraph for S2 = (4, 3). In this subgraph we will see that the sum will be equal to 4 + 1 +2 = 7 and that it covers all the vertices. Since it has the smallest sum out of all the spanning trees you can make over graph G, it will be the minimal spanning tree. A little notice here is that there could be many spanning tree's and minimal spanning tree's in a graph, which are often named subgraphs of the graph.

Comments

Post a Comment

Popular posts from this blog

Vigenère cipher encryption with C++

-
Image
Vigenère cipher is a substitution cipher that uses a 26 x 26 alphabetic table to either encrypt or decrypt. For example, say we wanted to encrypt the plaintext: "DAY" Then we would first pick an arbitrary keyword for the letter, let's go with: "SEE" From there on out, we would use the plaintext on the columns and keyword on the rows on the 26 x 26 table and then substitute. Ultimately, we would see that the plaintext combined with the keyword turns into: "VEC" Which will be our final encrypted text. An illustration of this can be seen visually as: Now, let's move over to the C++ program and start with main.cpp. main.cpp #include "Vigenere.h" Vigenere * vigenere = nullptr; int main () { vigenere = new Vigenere(); while (vigenere -> isRunning()) { vigenere -> showMenu(); vigenere -> handleEvents(); } return 0 ; } In this case, we're simply creating a new instance of a Vigenere object that we're g
Read more