北京邮电大学计算机学院 离散数学 9.1~9.3-relations.ppt

* * College of Computer Science Technology, BUPT Composite of relations Exmaple 5 P540 Find the matrix representing the relations S ?R, where the matrices representing R and S are Example 6 Find the matrix representing the relation R2, where the matrices representing R is * * College of Computer Science Technology, BUPT * * College of Computer Science Technology, BUPT The Digraph of a Relation If A is a finite set and R is a relation on A. Draw a small circle, called a vertex, for each element of A and label the circle with the corresponding element of A. Draw an arrow, called an arc or edge, from vertex ai to vertex aj if and only if ai R aj. The resulting pictorial representation of R is called a directed graph or digraph of R. * * College of Computer Science Technology, BUPT Using Directed Graphs A directed graph or digraph G=(VG,EG) is a set VG of vertices (nodes) with a set EG?VG×VG of edges (arcs,links). Visually represented using dots for nodes, and arrows for edges. Notice that a relation R:A×B can be represented as a graph GR=(VG=A?B, EG=R). Matrix representation MR: Graph rep. GR: Joe Fred Mark Susan Mary Sally Node set VG(black dots) Edge set EG(blue arrows) * * College of Computer Science Technology, BUPT Example Let A = {1, 2, 3, 4} R = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4), (4, 1)} Then 2 4 3 1 * * College of Computer Science Technology, BUPT Example Find the relation determined by R = {(1, 1), (1, 3), (2, 3), (3, 2), (3, 3), (4, 3)} 2 4 3 1 * * College of Computer Science Technology, BUPT Definitions If R is a relation on a set A and a ? A, then the in-degree of a (relative to the relation R) is the number of b ? A such that (b, a) ? R. the out-degree of a is the number of b ? A such that (a, b) ? R. * * College of Computer Science Technology, BUPT Example Let A = {a, b, c, d}, and R be the relation on A that has the matrix Construct the digraph of R, and list in-degrees and out-degrees of all