CISC 235 Lecture Notes - Lecture 16: Adjacency Matrix, Adjacency List, Complex Instruction Set Computing
32 views6 pages
15 Mar 2016
School
Department
Course
Professor
Document Summary
We saw most of the following definitions and notation in cisc: this information is included here for completeness. Graphs can be viewed as generalizations of trees (actually, trees are a subclass of graphs). A graph g consists of two sets: a set v of vertices, and a set e of edges, where each edge consists of a pair of vertices in v. Note that if we disallow duplicate edges, m is in o(n^2) Two vertices x and y are adjacent if (x,y) is in e. If x and y are adjacent, we call them neighbours. The degree of a vertex is the number of times the vertex appears in: if loops are prohibited (as is usual), the degree of a vertex is the number of edges that touch the vertex. We use d(v) to denote the degree of v. A path is a sequence of vertices and edges such that each edge joins the previous vertex to the next vertex.