Graphs and Networks Flashcards

1
Q

If a planar graph has 3 faces and 5 edges, how many vertices will it have? Show some justification of your answer.

A

V+F - e = 2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Identify the degree of each vertex in the graph

A

deg (A) = 0, deg (B) = 2, deg (C)= 2, deg (D) = 3, deg (E) = 3

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Draw a graph to represent the adjacency matrix shown below.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Create the adjacency matix

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Draw a graph that has four vertices and five edges, one of which is a loop

A

Many solutions. One is shown below

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is a planar graph?

A

A graph that has no crossovers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a path, trail, cycle

A

Path - walk that has no repeated edges or vertices

Trail - walk that has no repeated edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is an open/closed walk

A

Open - start and ends different vertex

Closed - start and end same vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is a semi-eularian graph

A

There is an open trail that touches every edge of the graph exactly once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is a eularian graph?

A

A graph that there is a path that touches every edge exactly once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly