Graph Theory and Project Scheduling Concepts

Minimum Spanning Tree

• The graph has 7 vertices (points) and 8 edges (lines) connected between them
• The minimum spanning tree is the tree with the lowest total weight (sum of all the numbers)
• The minimum spanning tree is found by connecting all the vertices with the smallest possible weights
• The weight of the minimum spanning tree is 30

Employee Duty Allocation

• Anthea, Bob, Cho and Dario are assigned duties 1, 2, 3 and 4
• The manager tries to allocate duties to minimise the total time to complete all duties
• The minimum total time is 29 minutes

Graph Planarity

• The adjacency matrix represents a graph
• The matrix displays connection between vertices
• The number of faces in the graph is 7

Project Scheduling

• The project has 10 activities to be completed
• The project network is a directed graph
• The directed graph shows the dependencies of activities and their predecessors
• The graph represents a sequence of activities with arrows connecting predecessors to successors
• Option D correctly shows the project's activity dependencies using a directed graph

Flow Network

• The network shows one-way paths through a maze
• Paths are from the entrance (A) to exit (H)
• Network has vertices (intersections) and connecting edges (paths)
• The capacity of a cut is the sum of capacities of edges across the cut
• The minimum cut capacity is the smallest possible capacity of all cuts
• The minimum cut capacity is 23
• Increasing the capacity of edge GH to 16 would lead to the greatest increase in flow

Matrix Operations

• Element m21 is the temperature for Week 2, Monday
• Matrix P is a permutation matrix, and matrix Q is a column matrix
• Multiplying Q by P rearranges the letters in Q
• Letters e, a and s change position

Markov Chains

• The transition matrix T models movement of birds between locations
• The rows of the transition matrix represent the starting location
• The columns represent the ending location
• The long-term outcome is that the number of birds will decrease at locations M and N and increase at location O

Matrix Inverses

• There are 4 statements about true and false statements regarding matrix inverses
• Two of the statements are true
• Not all square matrices have inverses
• The inverse of a matrix could be the same as the transpose of that matrix, but not always

Leslie Matrices

• The Leslie matrix models population distribution of a species
• Each column of the matrix represents an age class
• Each row represents the rate of change for that age class
• The element in the second row, first column represents the survival rate from the first year to the second year

School Lunch Transitions

• The transition diagram shows the proportion of students moving between four locations
• Numbers on the edges represent the maximum number of students allowed to move along that edge per minute
• The entrance and exit nodes allow for students to enter and leave the system
• The network could be used to track the flow of students through the different locations

This quiz covers essential topics in graph theory, including minimum spanning trees and graph planarity, as well as practical applications in project scheduling. Explore concepts such as duty allocation and project dependencies to deepen your understanding of efficient graph utilization.