Forming a graph model

Question

I came across a problem for which I don't know how to form a graph.

In one organization there are multiple members and it is known which of them is the president. The president has to from a hierarchic structure in which it will be known who is a supervisor to another member(only the president doesn't have a supervisor). For every pair of members there is a grade 1 or 10, (1 means they work pretty well with each other, 10 means they don't work well). It is very important for the president to form the structure in a way that the sum of all the grades between the pairs is minimal.
a) What kind of graph can you form for this problem? (Meaning directed or undirected) I think that it should be solved with an undirected graph.
b) Draw an example graph if there are 10 members and 15 pairs of members which work together(with a grade of 1 and 10).
c)With which algorithm can you find the minimal sum of the grades between the pairs? I think Kruskal's algorithm can work here.

Can someone give me an example of how to draw the graph? Thank you.

Answer 1

You're doing quite well.

• I agree with you that the graph of all of the members should be undirected. It's an interesting question because the subgraph that shows the hierarchy chart should be directed (or at least displayed as a rooted tree with the president as the root).

• If you're having trouble drawing the example graph, you're probably overthinking it. All you need is a graph with 10 vertices, 15 edges, and a label between 1 and 10 on every edge. If you want a particularly cool-looking graph that meets that criteria, here is the Petersen graph:

• You are also correct that Kruskal's algorithm is the proper strategy to generate a hierarchy where everyone except the president has a superior where they all get along as well as possible. As I mentioned before, when you have created that spanning tree, you will consider that tree as being rooted with the president as the root. Then everyone other than the president will report to the person one vertex closer to the president in the unique path along that spanning tree.