What's the word?
the proper name for the dot on a network
What is a Node or Vertice?
The edges and vertices create distinct areas.
What is a face?
Is node B connected to node C?
0 1 0 1
1 0 0 1
0 0 0 1
1 1 1 0
No
A graph that has a path where you can travel through every vertex exactly once, while ending at the initial vertex.
What is a Hamiltonian graph?
Step 1: begin at a vertex with low weighted edges
Step 2: progressively select edges with the lowest weighting (unless they form a circuit)
Step 3: continue until all vertices are selected
What is Prim's Algorithm?
a network with arrows on it
What is a directed graph?
The number of edges connected to a vertex
What is the degrees of a vertex?
How many faces will there be in a connected planar graph of 7 vertices and 10 edges?
5
The prefix used to describe when a path starts and finishes at a different vertex.
A sub-graph that identifies the lowest-cost connections that includes all of the vertices of the original graph
What is a minimum spanning tree?
A graph where it is not possible to move along the edges to every vertex.
What is a disconnected graph?
Used to determine if a graph is planar.
What is Euler's formula?
Draw a network for the following matrix.
*Mrs Monaghan will show the picture (Network2)
Teacher to check.
Answers Ex10.2 Q7b
All vertices have even degrees in this type of trail.
What is an Eulerian trail?
Identify the shortest distance to travel from A to D.
*Mrs Monaghan to show the picture (Network6)
11
A walk in which no edges are repeated.
How many faces does this Planar graph have?
*Mrs Monaghan will show picture (network3)
3
Any non-zero value in the leading diagonal of a matrix will indicate the existence of this.
What is a loop?
A garbage collection route is an example context for this.
What is a Eulerian trail?
Draw the minimum spanning tree for the graph shown.
*Mrs Monaghan will show the picture (Network5)
teacher to check
Example 9 pg360
When all vertices are connected to every other vertice.
What is a complete graph?
Redraw this graph so it is Planar.
*Mrs Monaghan will show the picture (Network1)
Teacher to check.
Construct an adjacency matrix for the following graph.
*Mrs Monaghan will show the picture (Network4)
0 0 1 1 2 0
0 0 1 0 0 1
1 1 0 0 0 0
1 0 0 0 0 3
2 0 0 0 0 0
0 1 0 3 0 0
Travelling to a list of European capital cities for sightseeing is an example context for this.
What is a Semi-Hamiltonian cycle?
A truck starts from the main distribution point at vertex A and makes deliveries at each of the other vertices before returning to A. What is the shortest route the truck can take?
*Mrs Monaghan will show the picture (Network7)
66