Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2012:journals:jeanpaul:chapterthreesectioni [2012/01/30 23:27] – mugabej | courses:cs211:winter2012:journals:jeanpaul:chapterthreesectioni [2012/01/30 23:46] (current) – mugabej |
|---|
| |
| |
| 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 //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. |
| |
| |
