Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:bairdc:chapter3 [2018/02/07 04:47] – bairdc | courses:cs211:winter2018:journals:bairdc:chapter3 [2018/02/07 04:58] (current) – bairdc | ||
|---|---|---|---|
| Line 75: | Line 75: | ||
| Overall I'd give this section a 7/10 on readability and interestingness. I thought it was a bit hard at times to follow the algorithms, but I got everything after a few read throughs. | Overall I'd give this section a 7/10 on readability and interestingness. I thought it was a bit hard at times to follow the algorithms, but I got everything after a few read throughs. | ||
| + | |||
| + | ===== 3.4 – Testing Bipartiteness: | ||
| + | |||
| + | A bipartite graph is one in which "the node set V can be partitioned into sets X and Y in such a way that every edge has one end in X and the other end in Y". Or, one in which every edge has one red end and one blue end. If a graph is bipartite, then it can't contain an odd cycle. Also, odd cycles are their only obstacles. The coloring algorithm to test for a bipartite graph is essentially BFS, moving outward from s and coloring nodes as they are encountered. | ||
| + | |||
| + | Overall I'd give this section a 10/10 on readability and interestingness. It was very concise and made complete sense. | ||
| + | |||
| + | ===== 3.5 – Connectivity in Directed Graphs ===== | ||
| + | |||
| + | When we represent directed graphs, each node will have 2 lists: one with nodes to which it has edges, and one from which it has edges. Something to note is that BFS and DFS are almost the same in directed graphs as they are in undirected graphs. A graph is strongly connected if, for every 2 nodes u and v, there is a path from u to v and one from v to u. 2 nodes are mutually reachable if there is a path from u to v and v to u, so a graph is strongly connected if every two nodes are mutually reachable. If u and v are mutually reachable, and v and w are mutually reachable, then u and w are mutually reachable. Also, for any 2 nodes s and t in a directed graph, their strong components are either identical or disjoint. | ||
| + | |||
| + | Overall I'd give this section a 10/10 on readability and interestingness. It was very concise and intuitive. | ||
| + | |||
| + | ===== 3.6 – Directed Acyclic Graphs and Topological Ordering ===== | ||
| + | |||
| + | Directed Acyclic Graphs (DAGs) are common in Computer Science because many kinds of dependency networks use them. A topological ordering of G is an ordering of its nodes as v1, v2, ..., vn so that for every edge (vi, vj), we have i < j. If G has a topological ordering, then G is a DAG. The converse of this holds as well. Also, in every DAG G, there is a node v with no incoming edges. You can repeatably remove v and find another v to find the topological order. | ||
| + | |||
| + | Overall I'd give this section a 9/10 on readability and interestingness. | ||
