1.7 Graphs

Basic Definitions

Definition

A graph $G=(V,E)$ consists of a set of vertices $V$ and a set of edges $E$. Each edge connects either two vertices (undirected) or is an ordered pair (directed).

Types of Graphs

Undirected Graph: $E\subseteq \left\{\{u,v\}\right|u,v\in V\}$.

Directed Graph Digraph: $E\subseteq V\times V$.

Simple Graph: No loops or multiple edges.

Multigraph: Allows multiple edges.

Weighted Graph: Each edge $e$ has a weight $w\left(e\right)\in ℝ$.

Vertex Degree

Degree undirected:
$\mathrm{deg}\left(v\right)=\left|\{\{v,u\}\in E\}\right|$.

In-degree/Out-degree directed:

${\mathrm{deg}}^{-}\left(v\right)=|\{u,v\}\in E|;{\mathrm{deg}}^{+}\left(v\right)=|\{v,u\}\in E|$

Paths and Cycles

Path: Sequence of vertices $v_0,v_1,\cdots ,v_k$ with $(v_{i-1},v_i)\in E$.

Simple Path: No repeated vertices.

Cycle: Path with $v_0=v_k$ and edges distinct.

Length: Number of edges in a path or cycle.

Connectivity

Undirected

Connected Graph: A path exists between every pair of vertices. Connected Component: Maximal connected subgraph.

Directed

Strongly Connected: Path in both directions between every pair.

Weakly Connected: Underlying undirected graph is connected.

Special Graphs

Complete Graph $K_n$: Every pair of distinct vertices is adjacent.

Complete Bipartite $K_{m,n}$: Bipartition $(V_1,V_2)$ with all cross edges.

Cycle Graph $C_n$: Single cycle of length $n$.

Path Graph $P_n$: Simple path with $n$ vertices.

Tree: Connected acyclic undirected graph.

Forest: Disjoint union of trees.

Planar Graph: Can be drawn without edge crossings.

Trees

Properties

• A connected graph with $n$ vertices and $n-1$ edges.

• Unique simple path between any two vertices.

• Equivalently, acyclic and $\left|E\right|=\left|V\right|-1$.

v $1.1$ Feb $27$