IB DP Maths: AI HL复习笔记3.10.1 Introduction to Graph Theory

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

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