3.2 Graph Models

Graph Models

A Simple Graph $G = (V (G), E (G))$ with $p$ vertices and $q$ edges consists of a vertex set (or a node set) $V (G) = {v_{1}, \dots, v_{p}}$ and an edge set $E (G) = {e_{1}, \dots, e_{q}}$ where each edge is an unordered pair of vertices

An edge $e = u, v$ is also denoted by $u v$ or $v u$

graph LR;
    u((u))---|e|v((v))

The vertices contained in an edge $e$ are its endpoints (or endnodes or endvertices), and $e$ is said to connect $u$ and $v$ . An edge $e = u v$ is said to be incident to its endpoints $u$ and $v$ . Two vertices that are endpoints of the same edge are said to be adjacent vertices, and two edges that are incident to the same vertex are said to be adjacent edges. Two adjacent vertices are also called neighbouring vertices.

Example

$G = (V (G), E (G))$
$V (G) = {v_{1}, v_{2}, v_{3}, v_{4}, v_{5}}$
$E (G) = {v_{1} v_{2}, v_{2} v_{3}, v_{3} v_{4}, v_{1} v_{4}, v_{2} v_{4} . v_{4} v_{5}}$

graph LR
v1((v1))
v2((v2))
v3((v3))
v4((v4))
v5((v5))
subgraph 1;
	direction LR;
	v2---v4
	v4---v5
	v1---v2
	v2---v3
	v3---v4
	v1---v4
end
V1((v1))
V2((v2))
V3((v3))
V4((v4))
V5((v5))
subgraph 2;
	direction RL;
	V1---V4
	V3---V4
	V4---V5
	V2---V3
	V1---V2
	V2---V4
end

Types of Graphs

Simple Graphs are unweighted and undirected. They also contain no loops or parallel edges

Multigraphs (or graphs or undirected graphs) allow loops and parallel edges

Directed graphs (or digraphs) ordered edges, which are called directed edges or arcs

graph LR
v1(( ))
v2(( ))
v3(( ))
v4(( ))
v1-->v2
v2-->v4
v2-->v3
v3-->v4
v4-->v1

Weighted Graphs: Each edge $e$ is assigned a weight $w (e)$

You can also have different combinations of the above models, such as directed weighted graphs, or weighted simple graphs