====== Week 3 ======

==== Chapter 3: Graphs ====
=== 3.1: Basic Definitions and Applications ===
An **undirected graph** is defined to be a set of **nodes** and a set of **edges**.  Each //edge// is defined to be a set of exactly two //nodes// that represent a direct relationship between them.
A **directed graph** is an //undirected graph// in which //edges// are ordered pairs instead of an unordered set of two //nodes//.  Thus, given any //edge// in a directed graph, traversal (or "flow") is only allowed from the start //node// to the end //node//.

=== 3.2: Graph Connectivity and Graph Traversal ===
**Breadth-first search** of a graph involves traversing a graph in such a way that when a node is visited, one of its children is immediately visited in a recursive fashion.  When a node is visited that doesn't contain any children, the search will backtrack back up through the parents of that node until it finds a node with children that haven't been visited yet.  This is usually accomplished with a stack that keeps track of the path from the start node to the current node being searched and each node is either marked or not marked to indicate whether or not it and its children have been visited already by the algorithm.

**Depth-first search** of a graph involves traversing a graph level by level in that every child of the current node is visited before traversing through those children's child nodes.  This is usually accomplished with a queue that keeps track of what nodes to traverse after all of the nodes in the current level of the graph have been traversed.

=== 3.3: Implementing Graphs ===
One way to represent a graph programmatically is through the use of an **adjacency matrix**.  Given a graph of //n// nodes and //m// edges, the adjacency matrix of that graph could be represented by a //n//x//n// matrix.  Each row and column of the matrix would represent a pair of vertices and a non-zero value at the corresponding coordinate in the matrix would represent an edge (while a value of zero at that coordinate would signify that there is no connection between the two nodes).

=== 3.4: Testing Bipartiteness: An Application of Breadth-First Search ===
:!: //Section 3.4 is a short section that talks about a specific use of the breadth-first search algorithm that checks a graph to determine if it is **bipartite**, meaning that the nodes can be organized into two distinct sets in which no two nodes within each set are connected by an edge.  I do not think it is necessary to include a summary on a section that is short in addition to being superfluous.//



~~DISCUSSION~~