Graphs, An Introduction

Introduction

A graph is a set of vertices V, and a set of edges E that connect pairs of points in V. Edges are actually determined by a symmetric irreflexive relation on V cross V. Some graphs may include loops (a point connected to itself) or multiple edges (many lines connecting a pair of points), but they are the exceptions. Unless otherwise indicated, the term "graph" refers to the definition above.

A digraph contains vertices and edges as above, but the edges are directed. In other words, the edge relation need not be symmetric. The edge v₁→v₂ does not imply the edge v₂→v₁. Edges are drawn using arrows, rather than line segments. Again, loops and multiple edges are usually prohibited.

A vertex has degree n if there are n edges connecting that vertex to other vertices. The number of edges is half the sum of the degrees.

In a digraph, vertices have indegrees and outdegrees. The number of directed edges is the sum of the indegrees, or the sum of the outdegrees.