2018 | OriginalPaper | Chapter

# 5. Graphs

Published in:
The Discrete Math Workbook

## Abstract

Graph is a pair \(G=\left( V,\;E\right) \), where V is a set of vertices (nodes), and E is a set of edges (arcs), connecting some pairs of vertices (nodes). A graph is said to be simple if it contains no loops (edges beginning and ending at the same vertex) and multiple edges (several edges are called multiple if they connect the same pair of vertices), and the sets V and E are finite. The figure where the graph vertices are shown as points, and edges are shown as segments or arcs, is called a diagram of a graph.

Two vertices u and v of a graph are adjacent is they are connected by an edge \({r=uv}\). In this case, it is said that the vertices u and v are endpoints of the edge r. If the vertex v is the endpoint of the edge r, then v and r are incident.

Directed graph or digraph is a pair \(D=(V, E)\), where V is a finite set of vertices, and E is a relation on V. Elements of the set E are called directed edges or arcs. An arc that connects a pair (u, v) of vertices u and v of the digraph D is denoted by uv. A simple digraph contains no loops (i.e., acrs of the form uu) or multiple arcs.