Font size
WorksheetsGraphs and Networks
Total questions: 120
Worksheet time: 2hrs 56mins
Choose the correct term to match each definition: Lines or curves that connect vertices.
Regions
Vertices
Edges
Paths
An edge that begins and ends at the same vertex.
Multiple edges
Vertices
Loop
Node
When the edges have a numerical representation (to indicate length, time, capacity etc.).
Multiple edges
Weighted graph
Complete graph
Directed graph
When the edges have a numerical representation (to indicate length, time, capacity etc.).
Multiple edges
Weighted graph
Complete graph
Directed graph
No arrows are shown on the edges.
Directed graph
Weighted graph
Simple graph
Undirected graph
An undirected and unweighted graph with no multiple edges.
Undirected graph
Unweighted graph
Incomplete graph
Simple graph
A walk that doesn’t finish at the starting vertex.
Walk
Closed walk
Open walk
Trail
A walk that has no repeat use of edges or vertices (except perhaps to end at the starting vertex).
Path
Closed walk
Open walk
Trail
Every path is a trail.
TRUE
FALSE
A walk that has no repeated edges (but can
revisit vertices).
Path
Trail
Eulerian trail
Hamiltonian circuit
Every vertex in this network is (blank) to every other vertex.
adjacent
connected
planar
disconnected
Two vertices are called (blank) if they are attached directly by at least one edge.
adjacent
connected
planar
complete
If it is possible to create a walk from one vertex to any other vertex, the network must be ...
connected
planar
complete
disjoint
Graphs that have directed edges are called
multiple edges
simple graphs
digraphs
trees
If a (blank) is removed, it will leave the graph disconnected.
node
region
bridge
loop
A path that starts and finishes at the same vertex.
cycle
trail
closed walk
loop
An edge that starts and finishes at the same vertex.
node
loop
arc
multiple edges
The number of edges a walk, trail, path or cycle uses.
Multiple edges
Length
Degree
Order
Which edge is considered a bridge?
AB
BC
CD
BE
What does the following represent:
A-B-E-A-D-C
Path
Trail
Circuit
Cycle
What does the following represent:
A-B-C-D-B-A
Eulerian Trail
Path
Circuit
Walk
What does the following represent:
A−B−E−B−F
Walk
Path
Circuit
Cycle
Is this diagram correctly labelled?
Yes
No
In a network a Walk is any route taken through a network, including routes that repeat edges and vertices. What is a Trail?
A walk in which no vertices are repeated, except possibly the start and finish
A walk in which no edges are repeated
When the edges have a numerical representation (to indicate length, time, capacity etc.).
Multiple edges
Weighted graph
Complete graph
Directed graph
Every path is a trail.
TRUE
FALSE
A walk that has no repeated edges (but can
revisit vertices).
Path
Trail
Eulerian trail
Hamiltonian circuit
A walk that doesn’t finish at the starting vertex.
Walk
Closed walk
Open walk
Trail
A walk that has no repeat use of edges or vertices (except perhaps to end at the starting vertex).
Path
Closed walk
Open walk
Trail
What are the lines in a graph called?
Vertices
Edges
Euler Circuits
Euler Paths
Which of the following is not a network?
Diagram shows a type of graph.
What is the type of graph?
Weighted graph
Directed graph
Simple graph
Tree
The diagram shows the activities required to complete a factory process. A forward scan has been completed for the process.
The duration of activity H is missing. What value should appear?
13
14
15
16
The diagram shows the activities required to complete a factory process. A forward scan has been completed for the process.
When a backward scan is completed, what is the value of X?
20
22
24
25
The diagram shows the activities required to complete a factory process. A forward scan has been completed for the process.
What is the critical path?
ABJ
AEGJ
CDGJ
CDHJ
The diagram shows the activities required to complete a task from start to finish and each activity has the duration (in days) shown beside it.
What is the EST (Earliest starting time) for activity Q?
23
27
28
29
The diagram shows the activities required to complete a task from start to finish and each activity has the duration (in days) shown beside it.
What is the EST (Earliest starting time) for activity Q?
23
27
28
29
The diagram shows the activities required to complete a process from start to finish and each activity has a duration (in days) shown beside it.
What is the critical path?
IKLPQ
IJMPQ
IJMNOQ
IKLNOQ
The diagram shows the activities required to complete a process from start to finish and each activity has a duration (in days) shown beside it.
What is the float time for activity K?
1 day
2 days
3 days
4 days
A network flow diagram is shown.
Find the total weight of the cut labelled 1.
88
96
98
104
A network flow diagram is shown.
Find the total weight of the cut labelled 2.
88
96
114
140
A network flow diagram is shown.
What is the maximum flow of this network?
88
96
104
114
What does the term "critical path" refer to in the context of critical path analysis (CPA)?
Tasks that must take place within the set time to avoid project delays
Tasks that have no dependencies
Tasks that can be delayed without affecting the project
Tasks that are not included in the project planning stage
What advantage does critical path analysis offer in terms of project management efficiency?
It enables project managers to reduce the time lost between tasks
It guarantees the smooth completion of a project
It limits the extent of assistance with project management
It helps managers to construct network diagrams for complex projects
What is the significance of float time in project management?
It calculates the earliest start time (EST) for activities
It guarantees the smooth completion of a project
It allows for more flexible resource allocation
It identifies tasks that require close monitoring
What is the purpose of the earliest start time (EST) in critical path analysis?
To show the earliest time that an activity can begin
To guarantee the smooth completion of a project
To calculate the latest finish time (LFT) for an activity
To identify the critical path in a project
In critical path analysis, what is the latest finish time (LFT) used to determine for a specific activity?
The latest possible time that an activity can finish without delaying the overall project
The dependencies it may have with other tasks
The time required to complete the activity
The earliest time that an activity can begin
How does critical path analysis improve efficiency in production?
By limiting the number of tasks in a project
By guaranteeing the smooth completion of each project
By reducing the time lost between different tasks
By constructing network diagrams for small projects
TRUE OR FALSE
By constructing network diagrams for small projects
True
False
Which key term: denotes an event (or task), with the start and finish times of each activity in a network diagram.
Node
float
dummy activity
buffer
What type of tool is Critical Path Analysis?
Situational
Planning
Decision-making
What is float time in project management?
Float time is the amount of time a task can be delayed without affecting the project's deadline.
Float time refers to the time taken for project meetings.
Float time is the total time required to complete a project.
Float time is the time allocated for team breaks during a project.
How do you calculate total float for an activity?
LFT+Duration+EST
LFT-Duration+EST
LFT+Duration-EST
LFT-Duration-EST
What is the significance of float time in scheduling?
Float time is used to determine project costs.
Float time only applies to resource allocation.
Float time is significant as it allows for flexibility in task scheduling without impacting project deadlines.
Float time is irrelevant to project scheduling.
In a network diagram, what does a critical path represent?
The shortest path through a project network that determines the longest possible project duration.
A path that has no dependencies and can be completed at any time.
The longest path through a project network that determines the shortest possible project duration.
A path that includes all tasks in the project regardless of their duration.
How do you identify the critical path in a project?
The critical path is identified by determining the longest sequence of dependent tasks that must be completed on time for the project to finish on schedule.
The critical path is the shortest sequence of tasks in a project.
The critical path is identified by random selection of tasks.
The critical path is determined by the number of resources allocated to each task.
What is the formula for calculating free float?
EST of previous activity - duration - EST of the next activity
EST of next activity - duration - EST of the previous activity
EST of next activity +EST of the previous activity
EST of next activity + duration + EST of the previous activity
Explain the difference between total float and free float.
Free float is the total time a project can be delayed without affecting its budget.
Total float and free float are interchangeable terms used in project management.
Total float refers to the total time a project can be delayed without any consequences.
Total float is the total delay possible without affecting project completion; free float is the delay possible without affecting subsequent tasks.
How can float time impact project deadlines?
Float time has no effect on project deadlines.
Float time can help absorb delays in non-critical tasks, allowing project deadlines to be met.
Float time only applies to critical tasks.
Float time is irrelevant to project management.
What is the purpose of a network diagram in project management?
To define the project budget and resources.
To create a risk management plan for the project.
To assign team members to specific tasks.
To illustrate task dependencies and the project timeline.
Describe how to create a network diagram for a project.
Create a network diagram by identifying tasks, determining dependencies, and visually representing them with nodes and arrows.
Outline the project timeline with milestones.
Create a budget plan for the project.
List all project team members and their roles.
Describe how to create a network diagram for a project.
Create a network diagram by identifying tasks, determining dependencies, and visually representing them with nodes and arrows.
Outline the project timeline with milestones.
Create a budget plan for the project.
List all project team members and their roles.
The graph shown contains NO cycles.
True
False
The graph shown contains NO cycles.
True
False
Which of the following statements are TRUE about a minimal spanning tree?
Each branch has a weight.
Contains no cycles.
All vertices are connected.
The path results in the minimum total weight.
Create a minimal spanning tree, then find the minimum total cost.
30
39
47
50
Create a minimal spanning tree, then find the minimum total cost.
20
21
22
23
Using Kruskal’s algorithm, which edge should you choose second?
AE
BD
DE
AB
Which of the following graphs is a bipartite graph?
A graph with an odd-length cycle
A graph with no cycles
A graph with a single vertex
A complete graph with 5 vertices
A graph is bipartite if and only if it does not contain which of the following?
An even-length cycle
A self-loop
An odd-length cycle
A complete subgraph
Which of the following properties is true for all bipartite graphs?
They have an even number of vertices
They can be coloured using two colours such that no two adjacent vertices share the same colour
They contain at least one cycle
They are always connected
Which of the following is a real-world example of a bipartite graph?
A social network where people are connected if they are friends
A job assignment problem where jobs are connected to people who can perform them
A transportation network where cities are connected by roads
A computer network where computers are connected by cables
Consider a bipartite graph G=(U,V,E) . Which of the following statements is true?
U and V must have the same number of vertices
Every edge in E connects a vertex in U to a vertex in V
G must be a tree
G must be a complete graph
If a bipartite graph has 10 vertices and 15 edges, what is the maximum number of edges that can be added without losing its bipartite property?
10
15
20
25
Which of the following is NOT a characteristic of a bipartite graph?
It can be divided into two disjoint sets
It contains no odd-length cycles
It can be coloured with two colours
It must be a planar graph
In a bipartite graph, the sum of the degrees of all vertices in one set is equal to:
The number of vertices in the other set
The sum of the degrees of all vertices in the other set
Twice the number of edges
Half the number of edges
A bipartite graph can be used to model which of the following scenarios?
A group of students and the courses they are enrolled in
A network of computers connected by cables
A set of cities connected by highways
A family tree
Which of the following statements is true for a bipartite graph?
It can have self-loops
It can have multiple edges between the same pair of vertices
It can be disconnected
It must be a complete graph
In a bipartite graph, if one set has 5 vertices and the other set has 7 vertices, what is the maximum number of edges the graph can have?
12
35
25
30
What is the degree of vertex 4?
3
4
5
7
Which vertices are adjacent to E?
B and C
B, C, D, and A
B
A, B, C, D, F, G
Which is an example of a disconnected graph?
None are disconnected graphs
An edge that begins and ends at the same vertex.
Multiple edges
Vertices
Loop
Node
What is the weight of circuit A, B, C, A
4
10
6
8
A Hamilton Circuit must touch every __________ once and only once
Vertex
Edge
Loop
Degree
Which of the following is an example of a Hamilton Circuit starting at A?
A, G, C, B, A
A, B, C, D, E, F, D, C, G, A
A, B, C, G, F, E, D
A, G, F, E, D, C, B, A
Which of the graphs below is a spanning tree of this connected graph?
Does this graph contain an Euler Circuit?
Yes
No
The number of edges will always equal half the number of degrees.
True
False
Identify the number of edges a graph with a sum of degrees = 10 will have.
2
20
5
10
Which of the following sequence of vertices forms a path?
A,F,D,B
A,B,D,E,C
A,F,C
D,E,C
The degree of a vertex = the number of edges directly connected to that vertex
True
False
A loop has a degree of 2.
True
False
Identify a23
What is the dimension of this matrix?
2 x 3
3 x 2
6 x 1
1 x 6
Does this network have a loop? If so, where?
No
Yes, 2 of them, at A and C
Yes, 1 at A
Yes, 1 at C
Identify the number of edges that connect vertex C and vertex D
0
1
2
3
Identify the number of edges that connect vertex D and vertex A
0
1
2
3
How many routes are there from A to B for this network?
1
3
4
2
Consider the network above. What is its adjacency matrix?
A matrix that records the number of connections between vertices is called an
Adversity matrix
Answer matrix
Adjacency matrix
Awesome matrix
In an Adjacency matrix loops are counted as ___ edge.
one
two
three
four
How many faces does this graph have
1
2
3
4
Choose which network matches the adjacency matrix
Which vertex has a loop?
A
B
C
D
How many degrees does vertex B have?
2
3
4
6
The number of faces in the graph is?
1
2
3
4
Which vertices have loops?
B and D
A and B
A and C
C and D
In column and row C are all zeros. What can you tell about vertex C?
Vertex A connects with only two other vertices
Vertex C is not connected to any other vertices.
Vertex B does not connect to Vertex A
Vertex C is connected to all the other vertices
In column and row C are all zeros. What can you tell about vertex C?
Vertex A connects with only two other vertices
Vertex C is not connected to any other vertices.
Vertex B does not connect to Vertex A
Vertex C is connected to all the other vertices
The degree for vertex B is
5
3
4
2
The graph has four vertices A, B, C and D. Which of the following statements is NOT true?
This graph is connected
This graph contains multiple edges
The graph contains a loop
The graph contains a bridge
The graph is planar
