CT Week 9

📚

Graph Concepts

A graph is a collection of nodes (vertices) and edges connecting pairs of nodes. In computational thinking, graphs are used to model relationships and processes. For example, a graph can represent a network of students where nodes are students and edges represent friendships or collaborations.

The mentoring problem involves assigning mentors to mentees in a way that optimizes certain criteria, such as maximizing the overall benefit or ensuring each mentee gets the best possible mentor. In the context of student performance, this could mean pairing high-performing students with those who need help, creating a graph where edges represent mentoring relationships.

A dictionary in a matrix context refers to using a dictionary data structure to store matrix elements efficiently. For example, in a sparse matrix (where most elements are zero), a dictionary can store only the non-zero elements, reducing memory usage. This can be useful in student performance tracking where only a few students might need special attention or resources.

A directed graph (or digraph) has edges with a direction, indicating a one-way relationship. In student performance, a directed graph can model dependencies, such as prerequisite courses. If a student must complete Course A before Course B, there would be a directed edge from A to B.

An undirected graph has edges without direction, indicating a mutual relationship. In the context of student performance, an undirected graph can represent study groups where each edge shows that two students study together, without implying any hierarchy or direction.

A clique in a graph is a subset of vertices where every two distinct vertices are connected by an edge. In student performance, a clique could represent a group of students who all collaborate with each other, forming a tightly-knit study group.

A popular student in graph terms is a node with a high degree, meaning it has many edges connecting it to other nodes. In a student performance context, this could be a student who collaborates with many peers or is frequently sought after for help.

Incoming edges (or in-degree) of a node are edges directed towards the node. In student performance, this could represent the number of students seeking help from a particular student.

Outgoing edges (or out-degree) are edges directed away from the node. This could represent the number of students a particular student is helping.