Maths Applications - Graphs and Networks

Simple Graph

a graph without any loops or multiple edges between adjacent vertices.

Connected Graph

any vertex can be reached using a sequence of edges, starting from any other vertex. Otherwise, the graph is disconnected.

Bridge

an edge that keeps the graph connected. If removed = disconnected.

Complete graph

a simple graph, where every vertex is connected to every other vertex. A compete graph with n vertices is called Kn.

Equation for no. of edges on complete graph

edges = n(n-1)/2 → where n = no. of vertices

Directed graph or Diagraph

directed edges also called arcs are drawn as arrows and represent one-way connection.

Undirected graph

undirected edges are drawn as lines and represent two-way connection.

Weighted graph

when edges of a graph are given some numerical values called weights that represent some property such as distance, cost, etc.

Subgraph

a graph formed using a subset of the vertices and edges in a larger graph. Cannot contain vertices and edges that are not in the original, larger graph.

Bipartite graph

graph with vertices that can be separated into two distinct sets, such that each edge of the graph only connects a vertex from one set to another. Vertices in one set are never connected to other vertices in the same set.

Complete Bipartite Graph

is a graph in which every vertex in the first group is connected to every vertex in the second group.

Planar Graph

are connected graphs that can be drawn so that they don’t have any edges crossing.

Regular Graph

each vertex has the same degree.

Topology

the study of networks

Vertices

Junctions/endpoints/dots (nodes)

Edges

lines/connects between vertices

Faces/regions

separate areas (outside = region)

Degree of a vertex

• No. of edges attached to the vertex

  • may be odd or even.

Rules of traversibility

• all vertices are even degree; or

• exactly two vertices are of odd degree and rest are even degree.

Loops

an edge that starts and ends at the same vertex.

Walk

most general definition of how we can move around a graph.

Open walk

a walk that starts and finishes at different vertices.

Closed Walk

a walk that starts and finishes at the same vertex.

Characteristics of walks

can include repeated edges and vertices.

Length

the number of edges a walk includes.

Trail

a walk where no edge is repeated (vertices can be repeated)

Open Trail

a trail that starts and ends at different vertices.

Circuit (closed trail)

a trail that starts and ends on the same vertex.

Path

a walk with no repeated edges and no repeated vertices.

Open path

a path that starts and ends at different vertices.

Cycle (closed path)

a path that starts and finishes at the same vertex.

Euler’s formula

v - e + f = 2
if the left side is equal to 2, then the graph is planar.

Eulerian Trail

a trail that includes every edge in a graph, but only once. May include repeated vertices.

Closed Eulerian Trail

an Eulerian trail that starts and finishes at the same vertex.

Eulerian Graph

a connected graph that contains a closed Eulerian trail. (every vertex has an even degree)

Open Eulerian trial

an Eulerian trail that starts and finshes at different vertices.

Semi - Eulerian trail

a connected graph that contains an open Eulerian trial. (exactly two vertices have an odd degree)

Hamiltonian path

a walk that includes every vertex of a graph exactly once (no repeated vertices).

Hamiltonian Cycle

a Hamiltonian path that starts and finishes at the same vertex.

Hamiltonian Graph

a connected graph that contains a Hamiltonian cycle.

Open Hamiltonian Path

A Hamiltonian path that finishes and starts at a different vertex.

Semi - Hamiltonian Graph

a connected graph that contains an open Hamiltonian path.