Basic Graph ADT

Table of contents

Definitions
1. Types of Graphs
Path
Simple Graph
Complete Graph
1. Number of Edges in a Complete Graph
Comparison to Trees
Forest
Sparse and Dense Graphs
1. Density of Graphs

Definitions

Let $G = (V, E)$ be a graph.

$V$ is a set of vertices.
$E$ is a set of edges.

Types of Graphs

Undirected Graph: edges have no direction
Directed Graph: edges have direction
Weighted Graph: edges have weights
Unweighted Graph: edges have no weights
Cyclic Graph: contains a cycle
Acyclic Graph: does not contain a cycle
Connected Graph: there is a path between every pair of vertices
Complete Graph: every pair of vertices is connected by an edge

Path

We call a sequence of edges connecting vertices in a graph a walk.

A path is a walk where all connected vertices are unique.

Reachability

Vertex $v$ is reachable from vertex $u$ if there is a path from $u$ to $v$ .

Connected Graph

A graph is connected if there is a path between every pair of vertices.

Connected Components

A subgraph of $G$ is a connected component if every pair of vertices in the subgraph is reachable from another.

In addition, it must not be reachable to any other vertex outside the subgraph.

Cycle

A cycle is a path that starts and ends at the same vertex.

Simple Graph

A simple graph is an undirected graph with no self-loops or multiple/parallel edges.

Unless stated otherwise, the term graph refers to a simple graph.

Complete Graph

A complete graph is a simple graph where every pair of vertices is connected by a single unique edge.

Number of Edges in a Complete Graph

A complete graph with $n$ vertices has:

(\binom{n}{2}) = \frac{n (n - 1)}{2}

undirected edges.

Comparison to Trees

Graphs are more general than trees
- All trees are graphs
Trees are connected and acyclic
For $n$ vertices, a tree always has $n - 1$ edges
Unless otherwise specified, graphs are undirected

Bit of an Extra Notion in Computer Science

In mathematical graph theory, a tree is an undirected graph.

However, in computer science, a tree is usually deemed to be an ordered (rooted) and directed graph data structure, always having a path from the root to leaves.

Forest

A forest is a disjoint set of trees.

Sparse and Dense Graphs

Density of Graphs

Let $| V | = n$ and $| E | = m$ .

We define density $D$ of the graph $G = (V, E)$ as the ratio of the number of edges to the number of edges in a complete graph:

(\binom{n}{2}) = \frac{n (n - 1)}{2}

The density of undirected graph is:

$D_{U} = \frac{2 m}{n (n - 1)}$

The density of directed graph is:

$D_{D} = \frac{m}{n (n - 1)}$

Roughly speaking:

Sparse Graph: $m = O (n)$
- The density $0 \leq D < \frac{1}{2}$
Basically, there is a reasonable number of edges for the number of vertices.
Dense Graph: $m = O (n^{2})$
- The density $\frac{1}{2} \leq D \leq 1$
As graph approaches a complete graph, $m \approx n^{2}$ .