TAILIEUCHUNG - Lecture Discrete structures: Chapter 16 - Amer Rasheed

In this chapter, the following content will be discussed: Properties of relations; reflexive, symmetric and transitive relations; properties of “less than” relations; properties of congruence modulo 3; transitive closure of a relations. | (CSC 102) Lecture 16 Discrete Structures Previous Lecture Summery Basic concepts of relation Types of relations Relation on a set The inverse of a relation Representing relations using Digraphs N-ary Relations Today’s Lecture Properties of relations Reflexive, Symmetric and Transitive Relations Properties of “Less than” relations Properties of Congruence Modulo 3 Transitive closure of a relations Representing Relations Using Digraphs Definition A directed graph, or digraph, consists of a set V of vertices (or nodes) together with a set E of ordered pairs of elements of V called edges (or arcs). The vertex a is called the initial vertex of the edge (a, b), and the vertex b is called the terminal vertex of this edge. We can use arrows to display graphs. Example: Display the digraph with V = {a, b, c, d} and E = {(a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b)}. a b c d An edge of the form (b, b) is called a loop. Representing Relations Using Digraphs Representing Relations Using Digraphs Let A = {3, 4, 5, 6, 7, 8} and define a relation R on A as follows: For all x, y ∈ A, x R y ⇔ 2

• Cơ sở dữ liệu
• Discrete structures
• Lecture Discrete structures
• Cấu trúc rời rạc
• Discrete data
• Discrete mathematics
• Computer scientists
• Equivalence relations