Introduction to Graph Theory (DP IB Applications & Interpretation (AI)): Revision Note

Parts of a Graph

A graph is a mathematical structure that is used to represent objects and the connections between them. They can be used in modelling many real-life applications, e.g. electrical circuits, flight paths, maps etc.

What are the different parts of a graph?

• A vertex (point) represents an object or a place

  • Adjacent vertices are connected by an edge

  • The degree of a vertex can be defined by how many edges are connected to it

• An edge (line) forms a connection between two vertices

  • Adjacent edges share a common vertex

  • An edge that starts and ends at the same vertex is called a loop

  • There may be multiple edges connecting two vertices

Types of Graphs

What are the types of graphs?

• A complete graph is a graph in which each vertex is connected by an edge to each of the other vertices

• The edges in a weighted graph are assigned numerical values such as distance or money

• The edges in a directed graph can only be travelled along in the direction indicated

  • the in-degree of a vertex is the number of edges that lead to that vertex

  • the out-degree is the number of edges that leave from that vertex

• A simple graph is undirected and unweighted and contains no loops or multiple edges

• Given a graph G, a subgraph will only contain edges and vertices that appear in G

• In a connected graph it is possible to move along the edges and vertices to find a route between any two vertices

  • If the graph is strongly connected, this route can be in either direction between the two vertices

• A tree is a graph in which any two vertices are connected by exactly one path

• A spanning tree is a subgraph, which is also a tree, of a graph G that contains all the vertices from G