CS341 Lecture Notes - Induced Subgraph, Adjacency Matrix, Tree Traversal
16 Oct 2011
School
Department
Course
Professor
Document Summary
Directed and undirected graphs: an undirected graph, g = is the pair, v = set of distinct vertices, e = set of edges, for example: V = {t, u, v, w, x, y, z} E = {{u, v}, {u, w}, {v, w}, {v, y}, {x, z}} Directed and undirected graphs: a directed graph, g = , similar to an undirected graph except e is a set of ordered pairs, for example: E = {, , , , } I. e. the number of edges originating in v: the number of vertices of g adjacent to v is called the indegree of v. I. e. the number of edges ending at v. Representations of graphs: adjacency matrix: u v w x z t y. 1: assign each vertex an integer index (in this example, u = 1, v = 2, etc. , m[i, j] = 1 if i and j are neighbours, 0 otherwise.
