Purchase Solution

Various Graph Theory Questions

Not what you're looking for?

Ask Custom Question

Through the use of appropriate algorithms minimal spanning tree solutions and optimal networking routes are discovered and explained. The document contains detailed solutions and drawings to help understand how to use the included algorithms.

Purchase this Solution

Solution Summary

This solution includes the detailed steps to solving various discrete math graph theory questions. It includes minimal spanning trees, optimal paths, and optimal flow.

Solution Preview

** Please see the attached file for the complete solution response **

1. In creating minimal spanning trees its best to use either Prim's Algorithm or Kruskal's Algorithm.

Prim's is as follows:
Step 1: Pick any vertex as a starting vertex. (Call it S). Mark it with any given color, say red.

Step 2: Find the nearest neighbor of S (call it P1). Mark both P1 and the edge SP1 red. cheapest unmarked (uncolored) edge in the graph that doesn't close a colored circuit. Mark this edge with same color of Step 1.

Step 3: Find the nearest uncolored neighbor to the red subgraph (i.e., the closest vertex to any red vertex). Mark it and the edge connecting the vertex to the red subgraph in red.

Step 4: Repeat Step 3 until all vertices are marked red. The red subgraph is a minimum spanning tree.

And Kruskal's:
Step 1: Find the cheapest edge in the graph (if there is more than one, pick one at random). Mark it with any given color, say red.

Step 2: Find the cheapest unmarked (uncolored) edge in the graph that doesn't close a colored or red circuit. Mark this edge ...

Purchase this Solution


Free BrainMass Quizzes
Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.