Graph Types

Graphs can be classified based on how they are connected, whether the edges have weights, whether cycles exist, etc.

Simple Undirected §

%%🖋 Edit in Excalidraw, and the dark exported image%%

• A graph that is both undirected and simple, generally the most common form of graphs.
• The maximum number of edges $\max (|E|)=\frac{|V|(|V|-1)}{2}$, this happens when the graph becomes complete.
• The graph density is given by:

$$\text{density}(G)=\frac{|E|}{\max (|E|)}=\frac{|E|}{\frac{|V|(|V|-1)}{2}}=\frac{2|E|}{|V|(|V|-1)}$$

Simple Directed §

%%🖋 Edit in Excalidraw, and the dark exported image%%

• Both simple and directed
• Maximum edges (i.e. max size) is given by $\max (|E|)=|V|(|V|-1)$
  • This is precisely double the maximum of a simple undirected graph, because now for an edge $(a,b)$, we can have an extra edge $(b,a)$
• Graph density given by:

$$\text{density}(G)=\frac{|E|}{\max (|E|)}=\frac{|E|}{|V|(|V|-1)}=\frac{|E|}{|V|(|V|-1)}$$

Directed Acyclic Graph (DAG) §

%%🖋 Edit in Excalidraw, and the dark exported image%%

• Is directed and acyclic

Undirected §

• All edges are two-way
• $E$, the set of edges, is now a symmetric binary relation

Directed §

• Edges are one-way
• The set $E$ of edges is no longer symmetric, meaning the existence of $(u,v)$ does not imply $(v,u)$ exists.
• If both $(u,v)$ and $(v,u)$ exist, the graph has a two-way edge.
• Useful for irreversible transitions and states, as well as prerequisites.

Cyclic / Acyclic §

%%🖋 Edit in Excalidraw, and the dark exported image%%

• A graph which contains at least one cycle.
• Similarly, an acyclic graph is one that has no cycles.

Connected §

(Assuming the graph is simple)

• Every node can be reached from every other node.
• Minimum edges required: $|E|=|V|-1$
• Maximum degree per node is: $\max (\mathrm{deg}(v_i))=|V|-1$
• A bridge is an edge which, if deleted, causes the graph to become disconnected

Simple §

• No loops
• No parallel edges

Complete §

%%🖋 Edit in Excalidraw, and the dark exported image%%

• Must be simple undirected
• Every vertex is adjacent to every other vertex
• Degree (No. of edges incident to a vertex) = $|V|-1$
• Size: $|E|=\frac{|V|(|V|-1)}{2}$
• Are considered dense since $\text{density}(G)=\frac{|E|}{\max (|E|)}=1$

Weighted §

• Every edge in the graph has been assigned a weight, which is treated as the cost required to go from node $u$ to node $v$.
• Note that the weights are assigned arbitrarily, they can mean distance between graphs, or monetary cost, anything.

Dense / Sparse §

A graph is considered dense if it has many more edges than nodes, more specifically, if it’s density is approximately 1:

$$G\text{ is dense}⟺\text{density}(G)\approx 1⟺\frac{|E|}{\max (|E|)}\approx 1$$

In other words, if the graph approaches a complete graph

Similarly, a graph is considered sparse if it has many more nodes than edges, more specifically, when it’s density is approximately 0:

$$G\text{ is sparse}⟺\text{density}(G)\approx 0⟺\frac{|E|}{\max (|E|)}\approx 0$$

In other words, if the graph approaches a tree

K-Partite §

• Graph is divided into $k$ number of sets.
• All nodes in a set are disconnected

Tree §

Spanning Trees §

#tosee related to Linear Span?

• A subgraph of a graph, which contains all of the parent graph’s nodes and is also a tree.

Minimum Spanning Tree §

• A spanning tree that contains the lowest weight.

Coloured Graph §

#todo Cleanup

A method for managing conflicts of interest & resource allocation. In a coloured graph, adjacent vertices must have different colours

Chromatic Number: The minimum value of $k$ such that a $k$-coloured graph can exist for a given graph. Usually depicted as a gamma function $\gamma (G)=k$