Graphs

Introduction

A graph represents a collection of points and lines possibly joining occasional pairs of points. A graph is an ordered pair (V, E) of a set V of vertices or nodes and a set E of edges or lines, such that each element of E is a 2-element subset of V. A graph G consists of two types of elements, namely vertices and edges. Every edge has two endpoints in the set of vertices, and is said to connect or join the two endpoints. An edge can thus be defined as a set of two vertices (or an ordered pair, in the case of a directed graph - see Section Direction). The two endpoints of an edge are also said to be adjacent to each other. Denoted by G = (V, E). Captures pairwise relationship between objects. Graph size parameters: n = |V|, m = |E|.

Contents

Use

Example

A graph may be represented by the following nodes and edges.

A-B-C | D

The set V of vertices is

{A, B, C, D}

The set E of edges is

{{A, B}, {B, C}, {B, D}}

The graph may be uniquely specified as the ordered pair

( {A, B, C, D}, {{A, B}, {B, C}, {B, D}} )

Example

The set V of vertices is

{ 1, 2, 3, 4, 5, 6, 7, 8 }

The set E of edges is

{ {1,2}, {1,3}, {2,3}, {2,4}, {2,5}, {3,5}, {3,7}, {3,8}, {4,5}, {5,6} }
n = 8
m = 10