====== Graph Theory ====== A graph is a mathematical structure that models pairwise relations between objects. The objects are represented as vertices and relations between two objects are represented with edges. For example, a road network could be described with a graph, where the cities are vertices and the roads between them are edges. ===== Basic Definitions ===== **Definition** A **graph** is a pair $G = (V,E)$ where $V$ is a set of elements that are called vertices and $E$ is a set of pairs $(u,v)$ with $u,v \in V$ that are called edges between the vertices $u$ and $v$. If we change this definition so that $E$ contains ordered pairs $(u,v)$ then we have a **directed graph**, where each pair represents a directed edge from $u$ to $v$, often written as $u \to v$. If not the graph is known as an **undirected graph** and edges don't have a direction. The fact that $E$ is a set also means that there can only be one edge between two vertices. For that reason this is sometimes called a **simple graph** to distinguish it from **multigraphs** which can have duplicate edges. In an undirected graph, a vertex $u$ is called a **neighbour** of $v$ if there exists an edge $(u,v) \in E$ and we say that $u$ is **adjacent** to $v$. The **degree** of a vertex $u$ is it's number of neighbours. **Definition** A graph $G' = (E', V')$ is a **subgraph** of a graph $G = (E,V)$ if $E' \subseteq E$ and $V' \subseteq V$. If $G' \not=G$ then $G'$ is a **proper subgraph** of $G$. A **walk** is a sequence of vertices where each vertex is adjacent to the next one. A walk is called a **path** if each vertex is visited at most once. We say that a vertex $u$ is **reachable** from $v$ if there exists a walk between them. A graph is **connected** if any vertex is reachable from all the other vertices. A **component** of a graph is a maximal connected subgraph. Every graph consists of one or more components and two vertices are in the same component if there exists a walk between them. ==== Types of Graphs ==== Here are a few commonly used graph types in addition to the ones we have already described. A **weighted graph** is a graph where each edge has been assigned a numerical value. The values might for example be costs, distances or bandwidth. Such graphs often arise in problems such as finding shortest paths or the travelling salesman problem. A **bipartite graph** is a simple graph in which the vertices can be partitioned into two sets such that each vertex in one set is only neighbours with a vertex from the other set i.e. there are no edges between vertices in the same set. Such graphs are useful when modeling relations between two classes of objects. A **tree** is a connected acyclic graph. ===== Data Structures ===== The most common data structure for storing graphs is the **adjacency list**. An adjacency list is an array $A$ such that the value $A[i]$ is an array of indexes of the adjacent vertices to vertex number $i$. The standard (and simplest) implementation of an adjacency list uses singly linked list. Adjacency lists can be implemented using hash tables in which each vertex is mapped to an array of it's adjacent vertices. A vertex can thus be represented by any hashable object. The main alternative to adjacency lists is the **adjacency matrix**. ===== Whatever First Search ===== ===== Classifying Vertices and Edges ===== ===== Acyclic Graphs ===== ==== Topological Ordering ==== ===== Strong Connectivity ===== ===== Dijkstra's Algorithm ===== ===== Bellman-Ford Algorithm =====