Graphs and Networks

• A graph consists of points (called verticies or nodes) which are connected by lines (edges or arcs)
• If a graph has a number associated with each edge (usually its weight), then the graph is known as a weighted graph or network.
• A subgraph of G is a graph, whose verices belong to G and each of those whose edges belongs to G. It is simply a part of the original graph.- part of a graph
• The degree or order or valency of a vertex is the number of edges incident to it.
• If the degree of a vertex is even, we say it has a even degree. 

• A path is a finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, in which no vertex appears more than once. 
• A walk is a path in which you can return to verticies more than once. 
• A cycle(or circuit) is a closed 'path'. ie. the end verted of the last edge is the start vertex of the first edge.

• Two verticies are connected if there is a path between them. A graph is connected if all its verticies are connected. 
• A loop is an edge that starts and finishes at the same vertex. 
• A simple graph is one in which there are no loops and not habe more than one edge connecting any pair of verticies. 
• If the edges of a graph have a direction associated with them they are known as directed edges and the graph is known as a diagraph

• A tree is a connected graph with no cycles.

• A spanning tree of a graph, G, is a subgraph which includes all the verticies of G and is also a tree. 

• A bipartite graph consists of two sets of vertices, X and Y. The edges ony join verticies in X to verticies in Y, not verticies within a set. 
• A complete graph is a graph in which every vertex is directly connected by an edge to each of the other verticies. If the graph has n verticies the connected graph is denoted by kn.
• A complete bipartite graph in which there are rverticies in set X and s verticies in set Y
• Isomorphic graphs are graphs that show the same information but are drawn differently- they must have the same number of verticies of the same degree, and connected in the same way.

• An adjacency matrix records the numver rof direct links between verticies. 

• A distance matrix records the weights on the edges. Where there is no edge we write -

• A minimum spanning tree (MST) is a spanning tree such that the total length of its arcs (edges) is as small as possible. 
• It is sometimes called a minimum connector.
• Kruskals algorithm finds the shortest, cheapest, or fastest way of linking all the nodes into one system:

1. Sort all the arcs(edges) into ascending order of weight. 

2. Select the arc of least weight to start the tree.

3. Consider the next arc of least weight.

    -If it would form a cycle with the arcs selected reject it. 

    -If it does not form a cycle, add it to the tree. 

    -If there is a choice, consider each in turn. 

4. Repeat step 3 until all verticies are connecteed.

• Like kruskals algorith, Prims algorithm finds the MST, but it uses a different approach. 

1. Choose any vertex to start the tree. 

2. Select the arc of the least weight that willl join a vertex already in the tree to a vertex not yet in the tree. (if there is a choice of arcs equal weight-pick randomly)

3. Repeat step 2 until all veritcies are connected.

• You can apply prims algorithm to a distance matrix.
• Kruskals can NOT! 

1. Choose any vertex to start the tree. 

2. Delete the row in the matrix for the chosen vertex. 

3. Number the column of the chosen vertex.

4. Put a ring around the lowest undelted entry in the numbered column. -If there is a choice choose randomly. 

5. The ringed entry becomes the next arc to be added to the tree and becomes the new vertex. 

6. Repeat steps 2-5 until all rows are deleted. 

• Dijkstra's algorithm is used to find the shortest path between two verticies in a network.
• It is used to find the shortest, cheapest or quickest route. eg. shortest cycle route from A to B.
• The algorithm to find the shortest path from S to T in a network: 

1. Label the start vertex, S with the final label 0. 

2. Record a working value at every vertex, Y, that is directly connected to the vertex, X, that has just recieved its final label. 

working value= final value at previous vertex(X)  + weight of arc between                                                                                   previous vertex and this one (arc XY)

-If there is already a working value at Y, it is replaced if the new value is smaller.                - once a vertex has a final label it isn't revisited and other working values are not considered

3. Look at the working values of the verticies that don't have a final value yet. Pick the smallest and make this the final value of that vertex. 

4. Repeat steps 2 and 3 until the end vertex, T, has a final label.

5.To find the shortest path trace the route backwards. An arc is on the path if:

Weight of arc BA= B - A