# Graphs and Networks

- Created by: amy
- Created on: 12-03-13 17:16

## 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.

## Graphs and Networks

- 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.

## Graphs and Networks

- 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**

## Types of graph

- 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.

## Types of graph

- 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*r*verticies 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.

## Graphs and networks in a matrix

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

## Graphs and networks in a distance matrix

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

## Minimum spanning tree

- 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.

## Minimum spanning tree

- 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.

## Minimum spanning tree

- 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

**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

## Comments

No comments have yet been made