Graphs and Networks Flashcards
If a planar graph has 3 faces and 5 edges, how many vertices will it have? Show some justification of your answer.
V+F - e = 2
Identify the degree of each vertex in the graph
deg (A) = 0, deg (B) = 2, deg (C)= 2, deg (D) = 3, deg (E) = 3
Draw a graph to represent the adjacency matrix shown below.
Create the adjacency matix
Draw a graph that has four vertices and five edges, one of which is a loop
Many solutions. One is shown below
A national park in Africa contains a number of animal species. In the park:
• Lions eat meerkat, rat and gazelle
• Meerkats eat grubs and rat
• Gazelle eat grasses
• Elephant eat grasses
Draw a directed graph to represent the information above. Use a vertex to represent each animal and an arc to represeent the connection between them. The arrow of the arc should point to the animal that eats the other.
What is a planar graph?
A graph that has no crossovers
What is a path, trail, cycle
Path - walk that has no repeated edges or vertices
Trail - walk that has no repeated edges
What is an open/closed walk
Open - start and ends different vertex
Closed - start and end same vertex
What is a semi-eularian graph
There is an open trail that touches every edge of the graph exactly once
What is a eularian graph?
A graph that there is a path that touches every edge exactly once
The graph below shows towns represented by the vertices. The edges represent the train linkes between these towns. The number on the edges are the cost of train tickets, in dollars, to travel between towns.
a) What is the cost of travelling from town G to town I via town F?
b) What is the least cost of travelling from town A to town G?
c) What route should be taken in order to travel from town D to town H for the least possible cost?
