Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Graph

A graph consists of a set of vertices (nodes) and a set of edges, where each edge connects two vertices called its endpoints. Example: vertices are airports storing a three-letter code, and edges are flight routes storing the mileage.

Applications:

  • electronic circuits (printed circuit boards, integrated circuits)
  • transportation networks (highways, flights)
  • computer networks (LAN, the Internet) and social networks

Types of Graphs

TypeEdgesExample
Undirectedbi-directional links onlystreet system where every street is two-way
Directed (digraph)each edge goes from to street system with some one-way streets
Weightedeach edge has a number (weight)mileage between airports, driving distance

In a digraph an edge from to is an out-edge of and an in-edge of . Weights depend on the application and may in general be positive or negative.

Basic Terminology

Terms:

  • adjacent vertices: and are adjacent if an edge joins them (one hop away)
  • degree of a vertex: number of edges at that vertex, e.g. has degree 5
  • leaf: a vertex with degree 1
  • parallel edges: two edges with the same endpoints, e.g. and
  • self-loop: an edge from a vertex back to itself, e.g.
  • simple graph: a graph with no self-loops and no parallel edges
  • in a digraph, in-degree counts incoming edges and out-degree counts outgoing edges

How the graph is stored in a program is covered in Graph Representations.