CMPT 225 Lecture 3: Lecture 3
25 Jan 2019
School
Department
Course
Professor
Document Summary
Its length is n ( # of edges traversed) A simple path has all vertices distinct. Vertex s is reachable from t if there is a path. G is connected if for every u, v within v u is reachable from v. A cycle is a simple path from vertex v to v: simplest cycle is the self-loop (one vertex) Trees is a connected graph with no cycles. Fact: every tree with n nodes has n-1 edges. A rooted tree is a tree with a distinguished note (the root) the root may be seen as inducing a direction on the edges. K-ary if every node has <= k children. Binary if every node has at most 2 children. Ordered if children of every node are ordered: drawing a tree implicitly orders it. Sub-tree rooted at a: tree whose root is a, and containing all descendants of a and their edges.
