[table][br][tr][br][td][b]Factual Questions:[/b][br]What defines an adjacency matrix in graph representation?[br][br]How is a walk described in graph theory?[br][br]How does an adjacency matrix calculate k-length walks between vertices?[br][br]Compare adjacency matrices and weighted adjacency tables.[br][br]What is an Eulerian trail?[br][/td][br][br][td][b]Conceptual Questions:[/b][br]How do odd-vertex weighted graphs impact Eulerian path/circuit complexity?[br][br]How do walks, trails, paths, circuits, and cycles provide different graph traversal insights?[br][br]What role does the transition matrix play in understanding stochastic processes?[br][br]Why is the Travelling Salesman Problem a significant computational challenge?[br][br]How does the Chinese Postman Problem reflect real-world optimization needs?[br][/td][br][br][td][b]Debatable Questions:[/b][br]Is Prim's algorithm universally more efficient than Kruskal's for MSTs across graph types?[br][br]Are Eulerian trails/circuits more fundamental to graph theory than Hamiltonian paths/cycles?[br][br]How do weights in graphs affect finding optimal paths/circuits?[br][br]Are adjacency matrices the optimal graph representation in all computational scenarios?[br][/td][br][/tr][br][/table][br]

AHL 3.15[br][br]Adjacency Matrices: This is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not. For directed graphs, the direction of the edge is shown by placing a number (usually 1) in the corresponding position.[br]

Walks: In graph theory, a walk is a sequence of vertices and edges where each edge's endpoints are the preceding and succeeding vertices. A walk can visit the same vertex and traverse the same edge multiple times.[br][br]Number of k-length Walks: This refers to the count of all possible walks of exactly k edges between two vertices. If the graph is represented by an adjacency matrix A, then(A raised to the power of k) gives a new matrix where the entry in the i-th row and j-th column represents the number of k-length walks from vertex i to vertex j.

Weighted Adjacency Tables: These are like adjacency matrices but instead of just indicating the presence of an edge with a 1, the table includes weights on the edges which can represent various attributes like cost, distance, or time.

Weighted Graph with Odd Vertices: This refers to a graph where weights represent some value (like cost or distance) on the edges, and 'odd vertices' are those with an odd number of edges (odd degree). The context suggests that there may be a specific algorithm or method applicable to such graphs for traversing each edge at least once, possibly related to finding an Eulerian path or circuit in the graph

Transition Matrix: This matrix is used in stochastic processes and represents the probabilities of transitioning from one state (or vertex) to another in a Markov chain or a graph. For a strongly connected graph, it indicates how likely it is to move from one vertex to another in a single step.[br][br]For example, whilst studying for your IB Maths exam if there are three different states, [br]Study (S)[br]Take a Break (B)[br]Seek Help (H) [br][br]The Transition Matrix will represent the probabilities of moving from one state to another, and a corresponding graph will visualize these transitions.

AHL 3.16[br][br]Tree and Cycle Algorithms with Undirected Graphs: This refers to algorithms that operate on undirected graphs to identify trees (graphs with no cycles) and cycles (closed paths where the first and last vertices are the same).[br][br]Walks, Trails, Paths, Circuits, Cycles: These are different ways to traverse graphs.[br][br]• Walk: A sequence of edges and vertices wherein vertices (and possibly edges) can be repeated.[br]• Trail: A walk where no edges are repeated.[br]• Path: A trail where no vertices are repeated.[br]• Circuit: A trail that starts and ends at the same vertex.[br]• Cycle: A circuit that only repeats the starting/ending vertex.[br]

Eulerian Trails and Circuits: An Eulerian trail is a trail in a graph that visits every edge exactly once. If such a trail exists that starts and ends at the same vertex, it’s called an Eulerian circuit.

Hamiltonian Paths and Cycles: A Hamiltonian path is a path that visits each vertex in the graph exactly once; if the path is a cycle, then it’s called a Hamiltonian cycle.

Minimum Spanning Tree (MST) Graph Algorithms: These algorithms find a subset of the edges of a connected, undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Kruskal’s and Prim’s Algorithms: These are two different algorithms for finding the MST of a graph. Kruskal’s algorithm adds the shortest edge that doesn’t produce a cycle until all vertices are connected, while Prim’s algorithm grows the MST one vertex at a time, always choosing the cheapest edge to add.