Shawn Zhong

Shawn Zhong

钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • Projects
    • 2048 Game
    • HiMCM 2016
    • 登峰杯 MCM
  • Course Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Shawn Zhong

钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • Projects
    • 2048 Game
    • HiMCM 2016
    • 登峰杯 MCM
  • Course Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Math 240

Home / Mathematics / Notes / Math 240 / Page 2

10.1 Graphs and Graph Models

  • May 07, 2018
  • Shawn
  • Math 240
  • No comments yet
Graphs • Definition ○ A graph G = (V, E) consists of § a nonempty set V of vertices (or nodes) § and a set E of edges. ○ Each edge has either one or two vertices associated with it, called its endpoints. ○ An edge is said to connect its endpoints. • Example ○ This is a graph with four vertices and five edges. • Remarks ○ The graphs we study here are unrelated to graphs of functions studied in Chapter 2. ○ We have a lot of freedom when we draw a picture of a graph. ○ All that matters is the connections made by the edges, not the particular geometry depicted. ○ For example, the lengths of edges, whether edges cross, how vertices are depicted, and so on, do not matter ○ A graph with an infinite vertex set is called an infinite graph. ○ A graph with a finite vertex set is called a finite graph. We (following the text) restrict our attention to finite graphs. Graph Terminology • In a simple graph each edge connects two different vertices and no two edges connect the same pair of vertices. • Multigraphs may have multiple edges connecting the same two vertices. • When m different edges connect the vertices u and v, we say that {u,v} is an edge of multiplicity m. • An edge that connects a vertex to itself is called a loop. • A pseudograph may include loops, as well as multiple edges connecting the same pair of vertices. • Example ○ This pseudograph has both multiple edges and a loop. Directed Graphs • Definition: ○ An directed graph (or digraph) G = (V, E) consists of § a nonempty set V of vertices (or nodes) § and a set E of directed edges (or arcs). ○ Each edge is associated with an ordered pair of vertices. ○ The directed edge associated with the ordered pair (u,v) is said to start at u and end at v. • Remark: ○ Graphs where the end points of an edge are not ordered are said to be undirected graphs. Some Terminology (continued) • Definition ○ A simple directed graph has no loops and no multiple edges. • Example ○ This is a directed graph with three vertices and four edges. • Definition ○ A directed multigraph may have multiple directed edges. ○ When there are m directed edges from the vertex u to the vertex v, ○ We say that (u,v) is an edge of multiplicity m. • Example ○ In this directed multigraph the multiplicity of (a,b) is 1 and the multiplicity of (b,c) is 2. Graph Models: Computer Networks • When we build a graph model, we use the appropriate type of graph to capture the important features of the application. • We illustrate this process using graph models of different types of computer networks. • In all these graph models, the vertices represent data centers and the edges represent communication links. • To model a computer network where we are only concerned whether two data centers are connected by a communications link, we use a simple graph. • This is the appropriate type of graph when we only care whether two data centers are directly linked (and not how many links there may be) and all communications links work in both directions. • To model a computer network where we care about the number of links between data centers, we use a multigraph. • To model a computer network with diagnostic links at data centers, we use a pseudograph, as loops are needed. • To model a network with multiple one-way links, we use a directed multigraph. • Note that we could use a directed graph without multiple edges if we only care whether there is at least one link from a data center to another data center. Graph Terminology: Summary • To understand the structure of a graph and to build a graph model, we ask these questions: ○ Are the edges of the graph undirected or directed (or both)? ○ If the edges are undirected, are multiple edges present that connect the same pair of vertices? ○ If the edges are directed, are multiple directed edges present? ○ Are loops present? Other Applications of Graphs • We will illustrate how graph theory can be used in models of: ○ Social networks ○ Communications networks ○ Information networks ○ Software design ○ Transportation networks ○ Biological networks • It’s a challenge to find a subject to which graph theory has not yet been applied. • Can you find an area without applications of graph theory? Examples of Collaboration Graphs • The Hollywood graph models the collaboration of actors in films. ○ We represent actors by vertices and we connect two vertices if the actors they represent have appeared in the same movie. ○ We will study the Hollywood Graph in Section 10.4 when we discuss Kevin Bacon numbers. • An academic collaboration graph models the collaboration of researchers who have jointly written a paper in a particular subject. ○ We represent researchers in a particular academic discipline using vertices. ○ We connect the vertices representing two researchers in this discipline if they are coauthors of a paper. ○ We will study the academic collaboration graph for mathematicians when we discuss Erdős numbers in Section 10.4. Transportation Graphs • Graph models are extensively used in the study of transportation networks. • Airline networks can be modeled using directed multigraphs where ○ airports are represented by vertices ○ each flight is represented by a directed edge from the vertex representing the departure airport to the vertex representing the destination airport • Road networks can be modeled using graphs where ○ vertices represent intersections and edges represent roads. ○ undirected edges represent two-way roads and directed edges represent one-way roads. Biological Applications • Graph models are used extensively in many areas of the biological science. • We will describe two such models, one to ecology and the other to molecular biology. • Niche overlap graphs model competition between species in an ecosystem • Vertices represent species and an edge connects two vertices when they represent species who compete for food resources. • Example: This is the niche overlap graph for a forest ecosystem with nine species. • We can model the interaction of proteins in a cell using a protein interaction network. • In a protein interaction graph, vertices represent proteins and vertices are connected by an edge if the proteins they represent interact. • Protein interaction graphs can be huge and can contain more than 100,000 vertices, each representing a different protein, and more than 1,000,000 edges, each representing an interaction between proteins • Protein interaction graphs are often split into smaller graphs, called modules, which represent the interactions between proteins involved in a particular function. • Example: This is a module of the protein interaction graph of proteins that degrade RNA in a human cell.
Read More >>

9.6 Partial Orderings

  • May 07, 2018
  • Shawn
  • Math 240
  • No comments yet
Partial Orderings • Definition 1 ○ A relation R on a set S is called a partial ordering, or partial order, if it is reflexive, antisymmetric, and transitive. ○ A set together with a partial ordering R is called a partially ordered set, or poset, and is denoted by (S, R). ○ Members of S are called elements of the poset. • Example 1 ○ Show that the “greater than or equal” relation (≥) is a partial ordering on the set of integers. ○ Reflexivity: a≥a for every integer a. ○ Antisymmetry: If a≥b and b≥a , then a=b. ○ Transitivity: If a≥b and b≥c , then a≥c. • Example 2 ○ Show that the divisibility relation (∣) is a partial ordering on the set of integers. ○ Reflexivity § a∣a for all integers a. (see Example 9 in Section 9.1) ○ Antisymmetry § If a and b are positive integers with a | b and b | a, then a = b § (see Example 12 in Section 9.1) ○ Transitivity § Suppose that a divides b and b divides c. § Then there are positive integers k and l such that b = ak and c = bl § Hence, c=a(kl), so a divides c. § Therefore, the relation is transitive. ○ (Z^+, ∣) is a poset. • Example 3 ○ Show that the inclusion relation (⊆) is a partial ordering on the power set of a set S. ○ Reflexivity: A⊆A whenever A is a subset of S. ○ Antisymmetry: If A and B are positive integers with A⊆B and B⊆A, then A=B. ○ Transitivity: If A⊆B and B⊆C, then A⊆C. Comparability • Definition 2 ○ The elements a and b of a poset (S,≼) are comparable if either a ≼ b or b ≼ a. ○ a,b∈S so that neither a ≼ b nor b ≼ a, then a and b are called incomparable. • Definition 3 ○ If (S,≼) is a poset and every two elements of S are comparable ○ Then S is called a totally ordered or linearly ordered set ○ And ≼ is called a total order or a linear order. ○ A totally ordered set is also called a chain. • Definition 4 ○ (S,≼) is a well-ordered set if it is a poset such that § ≼ is a total ordering § every nonempty subset of S has a least element. Hasse Diagrams • A Hasse diagram is a visual representation of a partial ordering that leaves out edges that must be present because of the reflexive and transitive properties. • A partial ordering is shown in (a) of the figure above. • The loops due to the reflexive property are deleted in (b). • The edges that must be present due to the transitive property are deleted in (c). • The Hasse diagram for the partial ordering (a), is depicted in © Lexicographic Order • Definition ○ Given two posets (A_1,≼_1) and (A_2,≼_2) ○ The lexicographic ordering on A_1⨉A_2 is defined by specifying that ○ (a_1, a_2) is less than (b1,b2), that is, (a_1, a_2) ≺ (b_1,b_2), ○ either if a_1 ≺_1 b_1 or if a_1=b_1 and a_2 ≺_2 b_2. ○ This definition can be easily extended to a lexicographic ordering on strings (see text). • Example ○ Consider strings of lowercase English letters ○ A lexicographic ordering can be defined using the ordering of the letters in the alphabet ○ This is the same ordering as that used in dictionaries. ○ discreet ≺ discrete, because these strings differ in the seventh position and e ≺ t. ○ discreet ≺ discreetness, because the first eight letters agree, but the second string is longer. Well Ordered Induction • Theorem ○ If (S,≤) is a well ordered poset and P is a property s.t. ○ If P(y) is true for all y x, then P(x) is true ○ Then P is true for all elements in the poset • Example ○ Suppose that a_(m,n) is defined for (m,n)∈N×N § a_0,0=0 § a_(m,n)={■8(a_(m−1,n)+1&if n=0 and m 0@a_(m,n−1)+n&if n 0)┤ ○ Show that a_(m,n)=m+n(n+1)/2 is defined for all (m,n)∈N×N • Solution ○ Use induction ○ Basis Step § a_0,0=0+(0⋅1)/2 ○ Inductive Step § Assume that a_(m^′,n^′ )=m^′+(n^′ (n^′+1))/2 whenever § (m^′,n′) is less than (m,n) in the lexicographic ordering of N×N § If n=0, by the inductive hypothesis, we can conclude □ a_(m,n)=a_(m−1,n)+1=m−1+n(n+1)/2+1=m+n(n+1)/2 § If n 0, by the inductive hypothesis, we can conclude □ a_(m,n)=a_(m−1,n)+1=m+n(n−1)/2+n=m+n(n+1)/2 Maximal and Minimal Elements • Definition ○ If (S,≤) is a ordered poset then an element a is ○ Minimal if there is no element b s.t. b≤a, and b is not equal to a ○ Maximal if there is no element b s.t. a≤b, and b is not equal to a ○ Greatest if for every element b∈S, b≤a ○ Least if for every element b∈S, a≤b • Intuition ○ Minimal: No element is strictly smaller ○ Least: Every other element is bigger ○ Maximal: No element is strictly bigger ○ Greatest: Every other element is smaller • Example 1 ○ Let {2,4,5,10,12,20,25} ordered by divisibility relation ○ Which element of {2,4,5,10,12,20,25} are maximal and which are minimal? ○ Is there a least or greatest element? ○ Maximal: 12, 20, 25 ○ Minimal: 2,5 ○ No least or greatest element. • Example 2 ○ Given an example of a poset with no minimal element and two maximal elements? ○ {〖1,1〗^∗,0,−1,−2,−3,…} where 1≥0≥−1≥−2≥…, and 1^∗≥0≥−1≥−2≥… Topological Sorting • Definition ○ If (S,R) is a partial ordering and (S,R^∗ ) is a total ordering then we say that ○ The two are compatible if R is a subset of R^∗ • Theorem ○ Let S be a finite set ○ Every partial order R on S has a compatible total order R^∗ • Proof ○ Every nonempty finite partial order has a minimal element ○ This can be proved by induction on the size of S ○ We should build a total ordering of S be selecting § a_1 to be a minimal element of S § a_2 to be the minimal element of S−{a_1 } § a_i to be the minimal element of S−{a_1,a_2,…,a_(i−1) } § a_n to be the least available element of S ○ We set R^∗={(a_i,a_i )|j≥i}
Read More >>

9.5 Equivalence Relations

  • Apr 23, 2018
  • Shawn
  • Math 240
  • No comments yet
Equivalence Relations • Definition 1 ○ A relation on a set A is called an equivalence relation if ○ it is reflexive, symmetric, and transitive • Definition 2 ○ Two elements a,b that are related by an equivalence relation are called equivalent ○ The notation a ∼ b is often used to denote that a and b are equivalent elements with respect to a particular equivalence relation. Strings • Example ○ Suppose that R is the relation on the set of strings of English letters such that ○ aRb if and only if l(a) = l(b), where l(x) is the length of the string x. ○ Is R an equivalence relation? • Solution ○ Show that all of the properties of an equivalence relation hold ○ Reflexivity § Because l(a)=l(a), it follows that aRa for all strings a. ○ Symmetry § Suppose that aRb. Since l(a)=l(b), l(b)=l(a) also holds and bRa. ○ Transitivity § Suppose that aRb and bRc § Since l(a)=l(b),and l(b)=l(c), l(a)=l(a) also holds and aRc. Congruence Modulo m • Example ○ Let m be an integer with m 1 ○ Show that the relation ○ R={(a,b)│a≡b (mod m) } ○ is an equivalence relation on the set of integers. • Solution ○ Recall that a≡b (mod m) if and only if m divides a−b ○ Reflexivity § a≡a (mod m) since a−a=0 is divisible by m since 0 = 0 ∙ m. ○ Symmetry § Suppose that a≡b (mod m) § Then a−b is divisible by m, and so a−b=km, where k is an integer § It follows that b−a=(−k)m, so b≡a (mod m). ○ Transitivity § Suppose that a≡b (mod m) and b≡c (mod m). § Then m divides both a−b and b−c. § Hence, there are integers k and l with a−b=km and b−c=lm § We obtain by adding the equations: § a−c=(a−b)+(b−c)=km+lm=(k+l)m § Therefore, a≡c (mod m) Divides • Example ○ Show that the “divides” relation on the set of positive integers is not an equivalence relation. • Solution ○ The properties of reflexivity, and transitivity do hold, but there relation is not transitive. ○ Hence, “divides” is not an equivalence relation. ○ Reflexivity § a ∣ a for all a. ○ Not Symmetric § For example, 2 ∣ 4, but 4 ∤ 2 § Hence, the relation is not symmetric. ○ Transitivity § Suppose that a divides b and b divides c. § Then there are positive integers k and l such that b=ak and c=bl. § Hence, c=a(kl), so a divides c. § Therefore, the relation is transitive. Equivalence Classes • Let R be an equivalence relation on a set A. • The set of all elements that are related to an element a of A is called the equivalence class of a • The equivalence class of a with respect to R is denoted by [a]_R. • When only one relation is under consideration, we can write [a], without the subscript R • Note that [a]_R={s|(a,s)∈R} • If b∈[a]_R, then b is called a representative of this equivalence class. • Any element of a class can be used as a representative of the class. • The equivalence classes of the relation congruence modulo m are called the congruence classes modulo m. • The congruence class of an integer a modulo m is denoted by [a]_m • So [a]_m={…,a−2m,a−m,a+2m,a+2m,…} • For example, ○ [0]_4 = {…, −8, −4 , 0, 4 , 8 , …} ○ [1]_4 = {…, −7, −3 , 1, 5 , 9 , …} ○ [2]_4 = {…, −6, −2 , 2, 6 , 10 , …} ○ [3]_4 = {…, −5, −1 , 3, 7 , 11 , …} Equivalence Classes and Partitions • Theorem 1 ○ Let R be an equivalence relation on a set A. ○ These statements for elements a and b of A are equivalent: i) aRb ii) [a]=[b] iii) [a]∩[b]=∅ • Proof ○ We show that (i) implies (ii). ○ Assume that aRb. ○ Now suppose that c ∈ [a].Then aRc. Because aRb and R is symmetric, bRa. ○ Because R is transitive and bRa and aRc, it follows that bRc. ○ Hence, c ∈ [b]. Therefore, [a]⊆ [b]. ○ A similar argument (omitted here) shows that [b]⊆ [a]. ○ Since [a]⊆ [b] and [b]⊆ [a], we have shown that [a] = [b]. Partition of a Set • A partition of a set S is a collection of disjoint nonempty subsets of S that have S as their union. • In other words, the collection of subsets A_i, where i∈I, forms a partition of S if and only if ○ A_i≠∅ for i∈I, ○ A_i∩A_j=∅ when i≠j, ○ ⋃8_(i∈I)▒A_i =S An Equivalence Relation Partitions a Set • Let R be an equivalence relation on a set A. • The union of all the equivalence classes of R is all of A • Since an element a of A is in its own equivalence class [a]_R. In other words, ○ ⋃8_(a∈A)▒[a]_R =A • From Theorem 1, it follows that these equivalence classes are either equal or disjoint • So [a]_R∩[b]_R=∅ when [a]_R≠[b]_R. • Therefore, the equivalence classes form a partition of A • Because they split A into disjoint subsets. Equivalence Relation and Partition • Theorem 2 ○ Let R be an equivalence relation on a set S. ○ Then the equivalence classes of R form a partition of S. ○ Conversely, given a partition {A_i│i∈I} of the set S ○ There is an equivalence relation R that has the sets A_i, i∈I, as its equivalence classes. • Proof ○ We have already shown the first part of the theorem. ○ For the second part, assume that {A_i│i∈I} is a partition of S. ○ Let R be the relation on S consisting of the pairs (x, y) ○ where x and y belong to the same subset A_i in the partition. ○ We must show that R satisfies the properties of an equivalence relation. ○ Reflexivity § For every a∈S, (a,a)∈R, because a is in the same subset as itself. ○ Symmetry § If (a,b)∈R, then b and a are in the same subset of the partition, so (b,a)∈R ○ Transitivity § If (a,b)∈R and (b,c)∈R, then a and b are in the same subset of the partition, as are b and c. § Since the subsets are disjoint and b belongs to both, the two subsets of the partition must be identical. § Therefore, (a,c)∈R since a and c belong to the same subset of the partition.
Read More >>

9.3 Representing Relations

  • Apr 23, 2018
  • Shawn
  • Math 240
  • No comments yet
Representing Relations Using Matrices • A relation between finite sets can be represented using a zero-one matrix. • Suppose R is a relation from A={a_1,a_2,…,a_m } to B={b_1,b_2,…,b_n } ○ The elements of the two sets can be listed in any arbitrary order ○ When A=B, we use the same ordering. • The relation R is represented by the matrix ○ M_R = [m_ij], where ○ m_ij={■8(1&if (a_i,b_j )∈R@0&if (a_i,b_j )∉R)┤ • The matrix representing R has ○ a 1 as its (i,j) entry when a_i is related to b_j ○ a 0 if a_i is not related to b_j. Examples of Representing Relations Using Matrices • Example 1 ○ Suppose that A = {1,2,3} and B = {1,2} ○ Let R be the relation from A to B containing (a,b) if a b. ○ What is the matrix representing R (with increasing numerical order) • Solution ○ Because R={(2,1), (3,1),(3,2)}, the matrix is ○ M_R=[■8(0&0@1&0@1&1)] • Example 2 ○ Let A={a_1,a_2, a_3} and B={b_1,b_2, b_3,b_4, b_5}. ○ Which ordered pairs are in the relation R represented by the matrix ○ M_R=[■8(0&1&0&0&0@1&0&1&1&0@1&0&1&0&1)] • Solution ○ Because R consists of those ordered pairs (a_i,b_j) with m_ij = 1 ○ R={(a_1, b_2), (a_2, b_1),(a_2, b_3), (a_2, b_4),(a_3, b_1), {(a_3, b_3 ), (a_3, b_5 )} Matrices of Relations on Sets • If R is a reflexive relation, all the elements on the main diagonal of M_R are equal to 1 • R is a symmetric relation, if and only if m_ij = 1 whenever m_ji = 1 • R is an antisymmetric relation, if and only if m_ij = 0 or m_ji = 0 when i≠j Example of a Relation on a Set • Example 3: Suppose that the relation R on a set is represented by the matrix ○ M_R=[■8(1&1&0@1&1&1@0&1&1)] • Is R reflexive, symmetric, and/or antisymmetric? • Because all the diagonal elements are equal to 1, R is reflexive • Because M_R is symmetric, R is symmetric • R not antisymmetric because both m_1,2 and m_2,1 are 1 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) ○ The vertex b is called the terminal vertex of this edge. ○ An edge of the form (a,a) is called a loop. Example 1 ○ A drawing of the directed graph with vertices a, b, c, and d ○ and edges (a, b), (a, d), (b, b), (b, d), (c, a), (c, b), and (d, b) is shown here. Example 2 ○ What are the ordered pairs in the relation represented by this directed graph? § ○ The ordered pairs in the relation are ○ (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (3, 1), (3, 3), (4, 1), (4, 3) Determining which Properties a Relation has from its Digraph • Reflexivity: A loop must be present at all vertices in the graph. • Symmetry: If (x,y) is an edge, then so is (y,x). • Antisymmetry: If (x,y) with x≠y is an edge, then (y,x) is not an edge. • Transitivity: If (x,y) and (y,z) are edges, then so is (x,z) Determining which Properties a Relation has from its Digraph • Example 1 ○ Reflexive? No, not every vertex has a loop ○ Symmetric? Yes (trivially), there is no edge from one vertex to another ○ Antisymmetric? Yes (trivially), there is no edge from one vertex to another ○ Transitive? Yes, (trivially) since there is no edge from one vertex to another • Example 2 ○ Reflexive? No, there are no loops ○ Symmetric? No, there is an edge from a to b, but not from b to a ○ Antisymmetric? No, there is an edge from d to b and b to d ○ Transitive? No, there are edges from a to c and from c to b, but there is no edge from a to d • Example 3 ○ Reflexive? No, there are no loops ○ Symmetric? No, for example, there is no edge from c to a ○ Antisymmetric? Yes, whenever there is an edge from one vertex to another, there is not one going back ○ Transitive? No, there is no edge from a to b • Example 4 ○ Reflexive? No, there are no loops ○ Symmetric? No, for example, there is no edge from d to a ○ Antisymmetric? Yes, whenever there is an edge from one vertex to another, there is not one going back ○ Transitive? Yes (trivially), there are no two edges where the first edge ends at the vertex where the second edge begins Closures • Definition ○ The closure of a relation R on A with respect to property P ○ is the least relation on A that contains R and has property P • Note ○ Least relation R^′ on A s.t. ○ R⊆R′ ○ R′ has property P ○ If S is a relation that safisfies the condition above, then R^′⊆S • Example ○ The reflexive closure of R is just R∪{(a,a)│a,∈A} ○ The symmetric closure of R is R∪R^(−1) ○ The transitive closure of R is R∪R^2∪R^3∪… Path in Directed Graphs • Definition ○ A path from a to b is a directed graph G is a sequence of edges ○ (a=x_0,x_1 ),(x_1,x_2 ),…,(x_(n−1),x_n=b) where n 0 ○ We denote the path by x_0,x_1,…,x_n say that the path has length n • Theorem ○ Let R be a relation on a set A ○ There is a path of length n from a to b if and only if (a,b) is an element of R^n The Connectivity Relation • Definition ○ Let R be a relation on A ○ The connectivity relation R^∗ cibsusts if all elements (a,b) s.t. ○ There is a path from a to b in R ○ In other words, R^∗ is the union of R,R^2,R^3,… ○ R^∗=⋃24_(i=1)^∞▒R^((i) ) • Example 1 ○ Let R be the relation between US state such that (a,b) is in R if a and b share a border. What is R^∗? ○ All pairs of states except Alaska and Hawaii • Example 2 ○ Let R be the relation between integers s.t. (a,b) is in R if b=a+1 ○ What is R^2, R^n, R^∗ ○ R^2={(a,b)│b=a+2} ○ R^n={(a,b)│b=a+n} ○ R^∗={(a,b)│a b} • Transitive closure ○ The connectivity relation R^∗ is exactly the transitive closure of R ○ We need to show that R is a subset of R^∗, R^∗ is transitive and least with that property. ○ The first two are easy ○ Let S be a transitive relation containing R ○ By induction we show that S contains R^n for every n Computing The Connectivity Relation • Theorem ○ Let R be a relation on A and let n be the number of elements in A. ○ The connectivity relation R^∗ is the union of R,R^2,…,R^n • Proof ○ Let (a,b) be the element of R^∗ ○ Let a_0=x_0,x_1,…,x_m=b be the shortest path witnessing this. ○ If m n, then two of the vertices among x_1,…,x_m must be the same, say x_i=x_j ○ But then we can find a shorter path x_0,x_1,…,x_i=x_j,x_(j+1),x_n • Corollary ○ M_(R^∗ )=M_R∨M_R^[2] ∨…∨M_R^[n] • Example ○ Compute M_(R^∗ ) for the relation R={(a,b),(b,c),(c,d),(d,b)} ○ M_R=[■8(0&1&0&0@0&0&1&0@0&0&0&1@0&1&0&0)] ○ M_R^[2] =[■8(0&1&0&0@0&0&1&0@0&0&0&1@0&1&0&0)]⨀[■8(0&1&0&0@0&0&1&0@0&0&0&1@0&1&0&0)]=[■8(0&0&1&0@0&0&0&1@0&1&0&0@0&0&1&0)] ○ Similarly, compute M_R^[3] ,M_R^[4] ○ Then M_(R^∗ )=M_R∨M_R^[2] ∨M_R^[3] ∨M_R^[4]
Read More >>

9.1 Relations and Their Properties

  • Apr 18, 2018
  • Shawn
  • Math 240
  • No comments yet
Binary Relations • Definition ○ A binary relation R from a set A to a set B is a subset R⊆A×B. • Example ○ Let A={0,1,2} and B={a,b} ○ {(0, a), (0, b), (1, a), (2, b)} is a relation from A to B. ○ We can represent this relation graphically or using a table: • Note ○ Relations are more general than functions ○ A function is a relation where exactly one element of B is related to each element of A Binary Relation on a Set • Definition ○ A binary relation R on a set A is a subset of A×A or a relation from A to A. • Example 1 ○ Suppose that A={a,b,c} ○ Then R={(a,a),(a,b), (a,c)} is a relation on A • Example 2 ○ Let A={1, 2, 3, 4} ○ The ordered pairs in the relation R={(a,b)│a divides b} are ○ {(1,1), (1, 2), (1,3), (1, 4), (2, 2), (2, 4), (3, 3),(4,4)} • Question: How many relations are there on a set A? ○ Because a relation on A is the same thing as a subset of A×A ○ We count the subsets of A×A. ○ Since A×A has n^2 elements when A has n elements ○ And a set with m elements has 2^m subsets ○ There are 2^(|A|^2 ) subsets of A×A. ○ Therefore, there are 2^(|A|^2 ) relations on a set A. • Example 3 ○ Consider these relations on the set of integers: § R_1={(a,b)│a≤b} § R_2={(a,b)│a b} § R_3={(a,b)│a=b or a=−b} § R_4={(a,b)│a=b} § R_5={(a,b)│a=b+1} § R_6={(a,b)│a+b≤3} ○ Note § These relations are on an infinite set and each of these relations is an infinite set § R_5 can be viewed as a function § Our definition of a function f:A→B is a subset of A×B § Therefore every function is a relation ○ Which of these relations contain each of the pairs § (1,1), (1, 2), (2, 1), (1, −1), and (2, 2)? ○ Solution § (1,1) is in R_1, R_3, R_4, and R_6 § (1,2) is in R_1 and R_6 § (2,1) is in R_2, R_5, and R_6 § (1, −1) is in R_2, R_3, and R_6 § (2,2) is in R_1, R_3, and R_4 Reflexive Relations • Definition ○ R is reflexive if and only if (a,a)∈R for every element a∈A ○ Written symbolically, R is reflexive if and only if ○ ∀x[x∈U→(x,x)∈R] • Note ○ If A = ∅ then the empty relation is reflexive vacuously. ○ That is the empty relation on an empty set is reflexive! • Example ○ The following relations on the integers are reflexive: § R_1={(a,b)│a≤b} § R_3={(a,b)│a=b or a=−b} § R_4={(a,b)│a=b} ○ The following relations are not reflexive: § R_2={(a,b)│a b} (note that 3 ≯ 3) § R_5={(a,b)│a=b+1} (note that 3 ≠ 3 + 1) § R_6={(a,b)│a+b≤3} (note that 4+4≰3) Antireflexive Relations • Definition ○ R is antireflexive if and only if (a,a)∉R for every element a∈A ○ Written symbolically, R is antireflexive if and only if ○ ∀x[x∈U→(x,x)∉R] • Note ○ Antireflexive is different from not reflexive • Example ○ The following relations on the integers are antireflexive § R_2={(a,b)│a b} § R_5={(a,b)│a=b+1} ○ R_6={(a,b)│a+b≤3} is neither reflexive nor antireflexive Symmetric Relations • Definition ○ R is symmetric if and only if (b,a)∈R whenever (a,b)∈R,∀a,b∈A ○ Written symbolically, R is symmetric if and only if ○ ∀x∀y[(x,y)∈R→(y,x)∈R] • Example ○ The following relations on the integers are symmetric: § R_3={(a,b)│a=b or a=−b} § R_4={(a,b)│a=b} § R_6={(a,b)│a+b≤3} ○ The following are not symmetric: § R_1={(a,b)│a≤b} (note that 3 ≤ 4, but 4 ≰ 3) § R_2={(a,b)│a b} (note that 4 3, but 3 ≯ 4) § R_5={(a,b)│a=b+1} (note that 4 = 3 + 1, but 3 ≠ 4 + 1) Antisymmetric Relations • Definition ○ R is antisymmetric if and only if a=b whenever (a,b),(b,a)∈R,∀a,b∈A ○ Written symbolically, R is antisymmetric if and only if ○ ∀x∀y[(x,y)∈R∧(y,x)∈R→x=y] • Note ○ For any integer, if a≥b and a≤b, then a=b • Example ○ The following relations on the integers are antisymmetric: § R_1={(a,b)│a≤b} § R_2={(a,b)│a b} § R_4={(a,b)│a=b} § R_5={(a,b)│a=b+1} ○ The following relations are not antisymmetric: § R_3={(a,b)│a=b or a=−b} (note that (1,−1),(−1,1)∈R_3) § R_6={(a,b)│a+b≤3} (note that (1,2),(2,1)∈R_6) Transitive Relations • Definition ○ R is transitive if and only if (a,c)∈R whenever (a,b),(b,c)∈R, ∀a,b,c∈A ○ Written symbolically, R is transitive if and only if ○ ∀x∀y∀z[(x,y)∈R∧(y,z)∈R→(x,z)∈R] • Note ○ For every integer, a≤b and b≤c, then b≤c • Example ○ The following relations on the integers are transitive: § R_1={(a,b)│a≤b} § R_2={(a,b)│a b} § R_3={(a,b)│a=b or a=−b} § R_4={(a,b)│a=b} ○ The following are not transitive: § R_5={(a,b)│a=b+1} (note that (3,2),(4,3)∈R_5, but (3,3)∉R_5), § R_6={(a,b)│a+b≤3} (note that (2,1),(1,2)∈R_6, but (2,2)∉R_6). Combining Relations • Given two relations R_1 and R_2 • We can combine them using basic set operations to form new relations • Example ○ Let A={1,2,3} and B={1,2,3,4} ○ The relations R_1 = {(1,1),(2,2),(3,3)} and R_2 = {(1,1),(1,2),(1,3),(1,4)} can be combined using basic set operations to form new relations: ○ R_1 ∪ R_2 ={(1,1),(1,2),(1,3),(1,4),(2,2),(3,3)} ○ R_1 ∩ R_2 ={(1,1)} ○ R_1 − R_2 ={(2,2),(3,3)} ○ R_2 − R_1 ={(1,2),(1,3),(1,4)} Inverse • Definition ○ Let R be a relation from A to B ○ The inverse of R is the relation § R^(−1)={(a,b)│(b,a)∈R} • Proposition ○ R is symmetric if and only if R=R^(−1) Composition • Definition ○ Suppose § R_1 is a relation from a set A to a set B. § R_2 is a relation from B to a set C ○ Then the composition of R_2 with R_1 is a relation from A to C where § if (x,y) is a member of R_1 § and (y,z) is a member of R_2 § then (x,z) is a member of R_2∘R_1 • Example ○ R_2∘R_1={(b,x),(b,z)} Powers of a Relation • Definition ○ Let R be a binary relation on A ○ Then the powers R_n of the relation R can be defined inductively by: ○ Basis Step: R_1=R ○ Inductive Step: R_(n+1)=R_n∘R • The powers of a transitive relation are subsets of the relation • This is established by the following theorem: • Theorem 1 ○ The relation R on a set A is transitive iff R_n⊆R for n = 1,2,3… ○ (see the text for a proof via mathematical induction)
Read More >>
  • 1
  • 2
  • 3
  • 4
  • …
  • 9

Search

  • Home Page
  • Tutorials
  • Mathematics
    • Math 240 - Discrete Math
    • Math 375 - Linear Algebra
    • Math 431 - Intro to Probability
    • Math 514 - Numerical Analysis
    • Math 521 - Analysis I
    • Math 541 - Abstract Algebra
    • Math 632 - Stochastic Processes
    • Abstract Algebra @ 万门大学
    • Linear Algebra @ 万门大学
    • Category Theory
  • Computer Sciences
    • CS/ECE 252 - Intro to Computer Engr.
    • CS/ECE 352 - Digital System Fund.
    • Learn Haskell
  • Projects
    • 2048 Game
    • HiMCM 2016
    • 登峰杯 MCM
  • Course Notes
    • AP Macroeconomics
    • AP Microeconomics
    • AP Chemistry
    • AP Statistics
    • AP Physics C: E&M
    • AP Physics C: Mechanics
    • CLEP Psychology

WeChat Account

Categories

  • Notes (418)
    • AP (115)
      • AP Macroeconomics (20)
      • AP Microeconomics (23)
      • AP Physics C E&M (25)
      • AP Physics C Mechanics (28)
      • AP Statistics (19)
    • Computer Sciences (2)
    • Mathematics (300)
      • Abstract Algebra (29)
      • Category Theory (7)
      • Linear Algebra (29)
      • Math 240 (42)
      • Math 375 (71)
      • Math 514 (18)
      • Math 521 (39)
      • Math 541 (39)
      • Math 632 (26)
  • Projects (4)
  • Tutorials (11)

Archives

  • October 2019
  • May 2019
  • April 2019
  • March 2019
  • February 2019
  • December 2018
  • November 2018
  • October 2018
  • September 2018
  • July 2018
  • May 2018
  • April 2018
  • March 2018
  • February 2018
  • January 2018
  • December 2017
  • November 2017
  • October 2017
  • September 2017
  • August 2017
  • July 2017
  • June 2017

WeChat Account

Links

RobeZH's thoughts on Algorithms - Ziyi Zhang
Copyright © 2018.      
TOP