Graph Types

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

Undirected Graphs §

• All edges are two-way

Directed Graphs (Digraphs) §

• Useful for irreversible transitions and states
• A → B exists, but B → A might not

Connected Graphs §

• Every node can be reached from every other node
• Minimum edges required: $|E|=|V|-1$
• A bridge is an edge which, if deleted, causes the graph to become disconnected

Simple Graphs §

• No loops
• No parallel edges

Complete Graphs §

• Every node is adjacent to every other vertex
• Degree (No. of edges incident to a vertex) = $|V|-1$
• Size: $|E|=\frac{|V|(|V|-1)}{2}$

K-Partite Graphs §

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

Tree §

• A graph containing no cycles
• Size must be: $|E|=|V|-1$

Spanning Trees §

• 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.