Table of Contents
Chapter 3
My notes on Chapter 3 readings
3.1: Basic Definitions & Applications
- Graphs are the coolest. A graph is a collection V of vertices and a collection E of edges such that each edge e∈E joins exactly two vertices in V.
- They can be used to model a lot of things:
- transportation networks
- communication networks
- information networks
- social networks
- dependency networks
- A path is a(n order-dependent) sequence of vertices such that there are edges between every consecutive pair of vertices in the sequence and that sequence gets you from one vertex to another.
- A cycle is a path from any vertex back to itself that contains at least two other vertices.
- A graph is then connected if there is a path in that graph connecting any two vertices.
- If the graph is directed, it's strongly connected if there's a path from any vertex u to any other vertex v, and vice versa.
- An undirected graph is a tree if it has no cycles.
- Every n-node tree has exactly n-1 edges
- A bipartite graph is a 2-colorable graph - you can color the vertices using two colors such that no two adjacent vertices are colored the same.
- I love graphs, so this section was an easy read. 10/10.
3.2: Graph Connectivity & Traversal
- Let's say we want to determine whether two vertices, s and t, are connected in a graph G. That is, whether there exists any path p in G such that both s and t are both on that path. How could we do this? We propose two algorithms to find all vertices in a connected component, starting at a vertex v.
- Breadth-first search: Add vertices one layer at a time in order of layer. Thus, add all vertices directly connected to v, then all vertices connected to something connected to v, and so on.
- There exists a path from v to some vertex t iff t is in some layer j.
- If two vertices are connected by an edge e in G, then those two vertices are at most one layer apart.
- The layer a vertex w is in is it's shortest path to vertex v.
- Depth-first search: Add vertices to the discovered vertices by going as far as you can from connected vertex to connected vertex. When you meet a dead-end, turn around and pick another connected vertex to search.
- Sets of connected components can be found by looking at a graphG, and placing all vertices discovered by either BFS or DFS for an arbitrary node, then exploring all nodes not yet discovered in the same way.
- We know that if two vertices are in G, their connected components are either the same or disjoint.
- Made sense in class, made sense in the book. 10/10.
3.3: Graph Traversal: Queues & Stacks
- We can represent a graph as either an adjacency list or an adjacency matrix.
- The list form requires O(n+m) for storage and vertex removal, O(n) for access, and O(m) for edge removal, but has constant-time addition of edges and vertices.
- The matrix requires O(n^2) for storage, vertex addition, and vertex removal, but has constant-time access, edge addition and edge removal.
- In spite of the fact that adjacency matrices seem worse, they're often preferred, especially to find all edges incident to a specific vertex.
- Both BFS and DFS take O(n+m) time complexity, where n represents the number of vertices and m the number of edges in G, assuming you use an adjacency list.
- Made sense in the book, kind of dry. 7/10.
3.4: Testing Bipartiteness
- Bipartite graphs contain no odd cycles.
- We can use breadth-first search to determine whether a graph is bipartite. We can then say:
- No edge of G joins two vertices of the same layer, thus G is bipartite and we can color the even layers one color and the odd another.
- xor
- An edge joins two vertices in the same layer, G contains an odd-length cycle, so G is not bipartite.
- This book section wasn't very interesting. 7/10.
3.5: Digraphs & Connectivity
- We represent digraphs as two adjacency lists, one of which is all in-edges and one of which is all out-edges.
- BFS & DFS are essentially the same now, with the following changes:
- BFS is given by finding all vertices with in-edges from our starting vertex to any other vertex.
- DFS is given recursively from vertex v by finding a vertex with an edge v → u.
- A digraph is strongly connected if for every pair of vertices (u,v) there exist paths u → v and v → u.
- If two vertices u,v are mutually reachable and v,w are mutually reachable, then u,w are mutually reachable.
- The strongly connected components of two vertices in a digraph D are either disjoint or identical.
- Well-written and interesting and delightful. 10/10.
3.6: Directed Acyclic Graphs & Topological Orderings
- A Directed Acyclic Graph is a directed graph without cycles. Go figure.
- They can be used to determine precedence relationships.
- A topological ordering of a directed graph G is an ordering of its nodes as v_1,v_2,…,v_n such that for each edge (v_i,v_j), i<j.
- Iff G is a DAG, it has a topological ordering.
- Every DAG necessarily has a vertex with no incoming edges.
- We compute topological orderings by finding a vertex in G without incoming edges, putting it first, and deleting it from G. Then recursively find a topo-ordering of G-v and appending that.
- This section was okay. 8/10.