A+ » VCE » Further Maths U3 & 4 Master Notes » OA2 Networks and Decision Mathematics » FM Connected Graph

# FM Connected Graph

## 3.1 Trees and Spanning Trees

Note: if you cannot remember what cycles or loops are, revise notes for 2.1 Introduction to Walks

### Trees

• A tree is a connected network graph which does not contain loops, multiple edges or cycles.
• One way of thinking about this, is that it is a graph that continuously branches out like a tree.
• Every connected graph will have at least one subgraph which is a tree.
• It uses the smallest number of edges to connect the graph.
• A tree with n vertices has n-1 edges.

Example

Read More »3.1 Trees and Spanning Trees

## 2.1 Introduction to Walks

### Walks

• A walk is a sequence of edges linking connected vertices in a graph.
• Walks can have repeated vertices and edges.
• Walks can be denoted in a written form by listing the vertices, in order, with a dash between each.
• Walks are shown graphically as a continuous line along each relevant edge. Arrows are placed along the line to show direction.

Example

The walk A-C-D-A-C is shown in the below graph:

### Connected Graph

Read More »2.1 Introduction to Walks

## 1.2 Further Concepts for Network Graphs

Note: if you cannot remember the basics of network graphs, revise notes for 1.1 Basics of Network Graphs.

### Simple Graph

• Graphs which do not contain loops or duplicate edges (i.e. there are no two vertices connected directly by more than one edge).
• Each vertex has a maximum degree of n-1.
• A simple graph has a maximum number of edges of \frac {n(n-1)}{2}.
• Graphs which contain loops or duplicate edges are sometimes called multigraphs.

Example

### Complete Graph

Read More »1.2 Further Concepts for Network Graphs