CSC263H1 Lecture Notes - Lecture 8: Adjacency Matrix, Directed Graph, Loop Invariant
18 Oct 2017
School
Department
Course
Professor
Document Summary
Csc 263 lecture summary for week 8 winter 2017. Graph g = (v,e): vertices/nodes v, edges/arcs e. Directed graph: e contains ordered pairs (u,v) in v^2; (u,v) != (v,u) and (v,v) (self-loops) allowed. Undirected graph: e contains unordered pairs {u,v} (_ v: {u,v} = {v,u} and {v,v} = {v} disallowed. Weighted graph: weight/cost w(e) in r for all e in e. Add a vertex; remove a vertex; add an edge; remove an edge. Neighbourhood (undirected graph): given vertex u, return set of vertices v such that {u,v} in e. In-neighbourhood/out-neighbourhood (directed graph): given vertex u, return set of vertices v such that (u,v)/(v,u) in e. Traversal: visit each vertex of a graph to perform some task. etc. Path = sequence of edges connected to each other: (v_1,v_2),(v_2,v_3),,(v_k,v_{k+1}) Simple path = no repeated edge or vertex. Cycle = path with end vertex = start vertex. Simple cycle = cycle with no repeated edge or vertex.
