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⊆{{u,v}|u,v∈V}.

Directed Graph Digraph: E⊆V×V.

Simple Graph: No loops or multiple edges.

Multigraph: Allows multiple edges.

Weighted Graph: Each edge e has a weight w(e)∈ℝ.

Vertex Degree

Degree undirected:
deg(v)=|{{v,u}∈E}|.

In-degree/Out-degree directed:

deg-*(v)=|{u,v}∈E|;deg+*(v)=|{v,u}∈E|

Paths and Cycles

Path: Sequence of vertices (v_0),(v_1),⋯,(v_k) with ((v_i-1),(v_i))∈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 |E|=|V|-1.