graph-theory

Introduction to graph theory

What is graph theory?

• Graph theory is the study of graphs, which are mathematical structures 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

Edges & vertices

What are the different parts of a graph?

• A graph is made up of a number of points (vertices or nodes) that are connected by lines (edges or arcs)

• A vertex (node) can represent an object, a place or a person

  • Adjacent vertices are connected by an edge 

  • Vertices are usually labelled with a letter, e.g. A, B, C…

    • The list of vertices in a graph is sometimes called the vertex set

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

  • Edges are described by the nodes they connect, e.g. AB, AC, BE…

    • The list of edges in a graph is sometimes called the edge set

  • Adjacent edges share a common vertex

  • There may be multiple edges connecting two vertices

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

• Typically a graph will be drawn such that edges do not overlap

  • Note that if a graph is drawn with overlapping edges, the edges are not connected at points where they overlap

  • Edges are only connected at vertices

Properties of graphs

What are the properties of graphs?

• The edges of a graph may be assigned a numerical value

  • This value is called the weight (of an edge)

  • Weight is often a measure such as distance, time or money

• A walk is a finite series of edges in a graph that starts at one vertex and moves from vertex to vertex

  • The (total) weight of a walk is the sum of the weights of the edges that it consists of

• A path is a walk where no vertex is visited more than once

• A trail is a walk where no edge is visited more than once

  • Every path is also a trail but not every trail is a path

• A cycle (or circuit) is a path that starts and finishes at the same vertex

  • It is also known as a closed path

• A tour is a walk that visits every vertex and returns to its start vertex

Types of graph

What are the types of graph?

• A connected graph is a graph in which all of its vertices are connected to each other

  • Two vertices are connected if there is a path between them

    • There does not need to be an edge connecting the pair of vertices

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

  • A complete graph with n vertices is labelled K_n

• If the edges of a graph have a weight, the graph is known as a weighted graph (or network)

  • Networks are not usually drawn to scale

• If the edges of a graph are assigned a direction, they are known as directed edges and the graph is known as a digraph

  • the directed edges of a graph can only be traversed in the direction indicated

• 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

• A tree is a connected graph that does not contain any cycles

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

• An isomorphic graph is a graph that shows the same information (number of vertices and valency of vertices) but is drawn in a different way

• A planar graph is a graph where no two edges meet each other except for at a vertex