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. The adjacency list data stxucture is ideal for implementing breadth-first search.P116

Finding the Set of All Connected Components We start with an arbitxary node s, and we use BFS to generate its connected component.then find a node v (if any) that was not visited by the search from s and iterate, using BFS (or DFS) starting from v to generate its connected component–which, by(3.8), will be disjoint from the component of s. We continue in this way until all nodes have been visited.

Interesting/Readable: 5 5

If there is an odd number cycle, then it is impossible to color them with differennt colors. Designing the algo Breadth-First Search The idea is to use the BFS to push the layers forward and test for bipartiteness. First we assume the graph G is connected, next we pick any node s that belongs to V and color it red. Color all the connected nodes on the next layer to be blue, and the next layer to be red. do this for the whole graph. The node cannnot be connected to any other nodes that are more than one layer away.

Interesting/Readable: 5 5

from undirected graphs to directed graphs Representing Directed Graphs: adjcentcy list: two lists in and out edges Breadth-first search and depth-first search are almost the same in directed graphs as they are in undirected graphs. Strong Connectivity: lemma:u and v are mutually reachable, and v and iv are mutually reachable then u and iv are mutually reachable. Proof on P124.

Interesting/Readable: 6 6

definitions:

• If a directed graph has no cycles, we call it–naturally enough–a directed acycIic graph, or a DAG.
• analogous to any dependant systems in problem solving
• DAGs can be used to encode precedence relations or dependencies in a natural way.

Problem: Goal: Find an algorithm for finding the TO. We can represent such an interdependent Set of tasks by introducing a node for each task, and a directed edge (i, j) whenever i must be done before j. The graph must be a DAG.

Preparation: G has a topological ordering, then G is a DAG. proof: contradiction, spse we have a topological ordering, and also a cycle. then see what happens to the max indexed nodes…see p126.

In every DAG G, there is a node v with no incoming edges. proof: same idea as above.

Algo Idea: find a node v with no incoming edges Order v first Delete v from G Recursively compute a topological ordering of G-{v} and append this order after v.

Readable/Interesting: 7/7