Your Practice Paper – Applications and Interpretation HL for IBDP Mathematics
18
Graph Theory
� Terminologies of graphs : Vertex : A point on a graph Edge : Arcs that connect vertices Walk : A sequence of edges Path : A sequence of edges that passes through any vertex and any edge at most once Degree of a vertex : Number of edges connecting the vertex Connected graph : A graph that there exists at least one walk between any two vertices Unconnected graph : A graph that there exist at least two vertices that there is no walk between them Subgraph of a graph : A collection of some edges and vertices of the original graph Loop : An edge that starts and ends at the same vertex Simple graph : A graph that has no loops and no multiple edges connecting the same pair of vertices Multiple graph : A graph that has multiple edges connecting at least one pair of vertices Cycle : A path that the starting vertex is the end vertex Tree : A connected graph with no cycles Spanning tree : A tree that connects all vertices in the graph
� Directed graphs : 1 . Directed graph : A graph that all edges are assigned with directions 2 . In-degree of a vertex : Number of edges connecting and pointing towards the vertex 3 . Out-degree of a vertex : Number of edges connecting and pointing away from the vertex
20
SE Production Limited