Intro to AGT

References

• Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein
  • “Some people are calling it the bible of algorithms” - An Algorithms Professor
• Graphs, Networks, and Algorithms (Springer series)
• Data Structures & Algorithms by K. Mehlhorn

Basic Graph Terms

A graph $G=(V,E)$ has:

• $V$: a set of vertices
• $E$: a set of edges

Order and Size

Undirected Graphs

An undirected, simple graph $G=(V,E)$ has:

• $V$: a set of vertices
• $E$: a set of edges, where each edge is a 2-element subset of $V$ ($\forall e\in E.e\subseteq V\wedge |e|=2.$)

Digraphs

Paths, Simple Paths, and Cycles

A path is a sequence of vertices where there are edges between adjacent vertices.

• Length is number of edges

A simple path is a path with distinct vertices.

Connectivity

An undirected graph is connected if there exists a $u-v$ path for all vertices $u,v$.

A digraph is connected if there exists a

• A digraph is strongly connected if there exists both a $u-v$ and $v-u$ path

Subgraphs

A graph $G^{\prime }=()$