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