Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:jeanpaul:chapterthreesectioni [2012/01/30 22:54] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterthreesectioni [2012/01/30 23:46] (current) – mugabej
@@ Line 6: / Line 6: @@
 ===Paths and Connectivity===
+  * A //path// in an undirected graph G = (V,E): A sequence P of nodes v<sub>1</sub>,v<sub>2</sub>,...,v<sub>k-1</sub>,v<sub>k</sub>, with the property that each consecutive pair v<sub>i</sub>,v<sub>i+1</sub> is joined by an edge in G.P is called a v<sub>k-1</sub> to v<sub>k</sub>. path.
+  * A //cycle//: a path v<sub>1</sub>,v<sub>2</sub>,...,v<sub>k-1</sub>,v<sub>k</sub> in which k>2, the first k-1 nodes are all distinct,and v<sub>1</sub> = v<sub>k</sub>. Both of the above definition are kept in the context of directed graphs, with the only difference being the fact that we must respect the directionality of edges.
+  * An undirected graph is //connected//: If for every pair of nodes u and v, there is a path from u to v.A directed graph is //strongly connected // if, for every two nodes u and v, there is a path from u to v and a path from v to u.
+  * //Distance// between two nodes u and v: the minimum number of edges in a u-v path.
+  * An undirected graph is a //tree// : If it's connected and doesn't contain a cycle.
+  * A node w in a tree is a //descendant// of w if v lies on the path from the root to w
+  * A leaf node: a node that has no descendants.
+Rooted trees express the notion of //hierarchy//. Every n-node tree has exactly n-1 edges.
+For an undirected graph G,any two of the statements below imply the third:\\
+  * G is connected
+  * G doesn't contain a cycle
+  * G has n-1 edges
+In brief, graphs are a very fundamental notion in the Computer Science field and requires attention from everyone interested in the field.\\
+Reading this section was pretty straightforward, as there aren't any confusing material in it. I definitely give it a 9/10.