Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2012:journals:garrett:entries:week_3 [2012/02/01 05:01] – section 3.5 garrettheath4 | courses:cs211:winter2012:journals:garrett:entries:week_3 [2012/03/07 03:44] (current) – added spacing garrettheath4 |
|---|
| :!: //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.// | :!: //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.// |
| |
| === 3.5: Connectivity in Directed Graphs === | |
| As noted in section 3.1, //undirected// graphs are just a special case of //directed// graphs in that an //undirected// has a set of //edges// such that for every edge ''(''//u//'', ''//v//'')'' there also exists an edge ''(''//v//'', ''//u//'')'', making every ''edge'' effectively bidirectional. | |
| |
| When a graph is described as being **strongly connected**, that means that for every pair of nodes in the graph there is a path of edges connecting one to the other and vice versa((The types of graphs where we consider how strongly connected it is are typically undirected graphs.)). | |
| |
| === 3.6: Directed Acyclic Graphs and Topological Ordering === | |
| A **directed acyclic graph** is defined to be a //directed// graph in which no cycles occur. Such graphs typically have a large number of edges compared to the number of nodes. Every //directed acyclic graph// has a **topological ordering** in which edges from nodes earlier in the order always point to nodes that occur later in the ordering. | |
| |
| ~~DISCUSSION~~ | ~~DISCUSSION~~ |
