Of Notes
Basic Graph Theory
Table of Contents
We build a graph
For a given graph we can compute things like:
- Order
which is the number of vertices - Size
which is the number of edges - Degree
which is the number of adjacent vertices
Importantly we also differentiate a simple graph which does not have any self-edges from a network with self-edges and multi-edges.
On the notation of edges, it is common to denote an edge
Sub-graphs (induced)
A subgraph is any graph
An induced subgraph however,
Definitions of Graphs
We have multiple notations and definitions of how to convey the shape of a graph… such as the matrix or set theoretic. Within these definitions we often talk about properties of graphs as-well:
- Directed
- Acyclic
Matrix Notation
This is the most basic notation of a graph which puts a one or zero where there is occurrence of an edge. We denote this matrix with
A rather simple example would be:
Where we only have two vertices and one edge.
Measuring Degrees
We leverage the Kronecker Delta Function to filter the matrix for properties we want.
Which give us the sum of the
For example the graph below, with edges
Set Theoretic
This is a more interesting notation for when we want to understand the number of inward or outward edges of each vertex.
We start with
From this we can then compute the in-degree by simply taking the size
It also stands that:
Graph Structure Characteristics
We begin to concern ourselves with the structure of a given graph. We start by asking questions like:
How many paths are there to connect
Assuming we have two nodes
Which by a matrix identity:
where the general formula is