A graph consists of a vertex set and edge set, i.e. $G = (V, E)$.

Graphs can be directed:

• directed means that edge $(u, v)$ does not imply edge $(v, u)$
• undirected means that edge $(u, v)$ implies edge $(v, u)$

Edges may be labelled (i.e. weighted).

Common Terminology

• Vertex (node)
• Edge (link) - connects one vertex to another (or itself)
• Given edge $(u,v)$:
  • $v$ is an out-neighbor of $u$
  • $u$ is an in-neighbor of $v$
• In-Degree(v) - how many edges lead into $v$
• Out-Degree(v) - how many edges lead out from $v$

Applications of Graphs

• Roadways, Water mains, power lines
• Social Networks (person is a vertex, edges are “friends”)
• Computer networks (the internet)

We observe that most “physical” systems involving graphs involve sparse graphs - number of edges is closer to $|V|$ then $|V|^2$.

Graph Representation