====== 3.1 Basic Definitions and Application ======
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



====== 3.2 Graph Connectivity and Graph Traversal ======
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

====== 3.3 Implementing Graph Traversal Using Queues and Stacks ======
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

====== 3.4 Testing Bipartiteness: An Application of Breadth-First Search ======
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

====== 3.5 Connectivity in Directed Graphs ======
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


====== 3.6 Directed Acyclic Graphs and Topological Ordering ======
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