The summary Motivation of a graph: easy in representing pair-wise relationships within a system. Definition of a graph (categories: undirected and directed) A graph consists of a number of nodes and edges. Edges in a graph indicate a symmetric relationship between their ends. Often we want to encode asymmetric relationships, and for this we use the closely related notion of a directed graph. Some example applications of the graph: • Transportation networks. The map of routes served by an airline carrier naturally forms a graph. • Communication networks. A collection of computers connected via a communication network can be naturally modeled as a graph. • Information networks. The World Wide Web can be naturally viewed as a directed graph, in which nodes correspond to Web pages and there is an edge from u to v if u has a hyperlink to v. • Social networks, the facebook example. • Dependency networks. Which we are going to cover later.

Paths and Connectivity Find out if there is a path between node A and node B. A tree is a graph without cycles.

Interesting/readable: 5 /5

Key issue: n0de-to-node connectivity Breadth-First Search We explore outward from s in all possible directions, adding nodes one “layer” at a time. Thus we start with s and include all nodes that are joined by an edge to s–this is the first layer of the search. We then include all additional nodes that are joined by an edge to any node in the first layer–this is the second. • The BFS produces a rooted tree from the node where it starts and including all nodes reachable from the root in all layers. • Another property of BFS: Let T be a breadth-first search tree, let x and y be nodes in T belonging to layers Li and Lj respectively, and let (x, y) be an edge of G. Then i and j differ by at most 1. (Which is a useful property when getting into examining bipartite graphs.) • Algorithm for finding the connected components

Depth-First Search Another natural method to find the nodes reachable from s is the approach you might take if the graph G were truly a maze of interconnected rooms and you were walking around in it. You’d start from s and try the first edge leading out of it, to a node u. You’d then follow the first edge leading out of u, and continue in this way until you reached a “dead end”–a node for which you had already explored all its neighbors. You’d then backtrack until you got to a node with an unexplored neighbor, and resume from there. We call this algorithm depth first search (DFS), since it explores G by going as deeply’ as possible and only retreating when necessary. • Use a stack instead of a queue data structure for storing the explored elements would change a BFS into a DFS. • It uses backtrack when it gets into a dead-end. • For any two nodes s and t in a graph, their connected components are either identical or disjoint. Proof in page 110 (cut version).

Readable/ Interesting: 6/6

Two approaches:

• Adjacency matrix • Adjacency list Tradeoffs: The adjacency matrix representation of a graph requires O (n2) space, while the adjacency list representation requires only O (m + n) space.