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
| Type | Edges | Example |
|---|---|---|
| Undirected | bi-directional links only | street system where every street is two-way |
| Directed (digraph) | each edge goes from to | street system with some one-way streets |
| Weighted | each 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.