Unit 6 Flashcards
1
Q
A binary relation is a way of expressing a blank between two sets
A
relationship
2
Q
Mathematically, a blankbetween two sets A and B is a subset R of A x B. The term binary refers to the fact that the relation is a subset of the Cartesian product of two sets.
A
binary relation
3
Q
For a ∈ A and b ∈ B, the fact that (a, b) ∈ R is denoted by blank.
A
aRb
4
Q
In an blank of a relation R on sets A and B, the elements of A are listed on the left, the elements of B are listed on the right, and there is an arrow from a ∈ A to b ∈ B if aRb.
A
arrow diagram
5
Q
A blank of relation R between A and B is a rectangular array of numbers with |A| rows and |B| columns. Each row corresponds to an element of A and each column corresponds to an element of B. For a ∈ A and b ∈ B, there is a 1 in row a, column b, if aRb. Otherwise, there is a 0.
A
matrix representation
6
Q
It is possible to have a relation between two sets A and B in which A = B. A binary relation on a set A is a subset of A x A. The set A is called the blank of the binary relation.
A
domain
7
Q
An arrow diagram for a relation R on a finite set A requires only one copy of the elements of A. There is an arrow from a to b if blank.
A
aRb
8
Q
An element that is related to itself is indicated by an arrow called a blank
A
self-loop
9
Q
The relation R is blank if for every x ∈ A, xRx.
A
reflexive
10
Q
The relation R is blank if for every x ∈ A, it is not true that xRx.
A
anti-reflexive
11
Q
The relation R is blank if for every x,y, z ∈ A, xRy and yRz imply that xRz.
A
transitive
12
Q
The relation R is blank if for every x,y ∈ A, xRy implies that yRx.
A
symmetric
13
Q
The relation R is blank if for every x,y ∈ A, xRy and yRx imply that x = y.
A
anti-symmetric
14
Q
Each of the properties of a binary relation is stated as a blank. Therefore in order to establish that relation has a property, the condition must be shown to be true for all the elements in the domain.
A
universal condition
15
Q
A blank (or digraph, for short) consists of a pair (V, E).
A
directed graph
16
Q
V is a set of blank, and E, a set of directed blank, is a subset of V × V.
A
vertices
edges
17
Q
An individual element of V is called a blank. A blank is typically pictured as a dot or a circle labeled with the name of the vertex.
A
vertex
18
Q
An blank (u, v) ∈ E, is pictured as an arrow going from the vertex labeled u to the vertex labeled v.
A
edge
19
Q
The vertex u is the tail of the edge (u, v) and vertex v is the head. If the head and the tail of an edge are the same vertex, the edge is called a blank.
A
self-loop
20
Q
The blank of a vertex is the number of edges pointing into it.
A
in-degree
21
Q
The blank of a vertex is the number of edges pointing out of it.
A
out-degree
22
Q
A blank from v0 to vl in a directed graph G is a sequence of alternating vertices and edges that starts and ends with a vertex.
A
walk
23
Q
The blank of a walk is l, the number of edges in the walk.
A
length
24
Q
An blank is a walk in which the first and last vertices are not the same.
A
open walk
25
A blank is a walk in which the first and last vertices are the same.
closed walk
26
A blank is an open walk in which no edge occurs more than once.
trail
27
A blank is a closed walk in which no edge occurs more than once.
circuit
28
A blank is a trail in which no vertex occurs more than once.
path
29
A blank is a circuit of length at least 1 in which no vertex occurs more than once, except the first and last vertices which are the same.
cycle
30
cycle
31
The circuit
is blank because the vertex a appears in the middle of the circuit as well as at the beginning and the end.
not a cycle
32
The circuit
is also blank because the vertex c is repeated in the middle of the circuit.
not a cycle
33
A blank is a link between two sets and is a collection of ordered pairs that contains one object from each of the given set. The arrow diagram for a binary relation is a directed graph.
relation
34
The blank of binary relations is a concept of forming a new relation from two given relations.
composition
35
The composition of two relations, B and W, on set Y is denoted blank
.
W o B
36
The ordering of a composition is to apply the output of the blank function as the input to the blank function.
second
first
37
Let G be a directed graph. Let u and v be any two vertices in G. There is an edge from u to v in Gk if and only if there is a walk of length k from u to v in G is what theorem
The Graph Power Theorem
38
The relation R+ is called the blank and is the smallest relation that is both transitive and includes all the pairs from R. In other words, any relation that contains all the pairs from R and is transitive must include all the pairs in R+.
transitive closure of R
39
If G is a directed graph, then G+ is called the blank. The animation below shows how the graph G+(with 4 vertices) is determined from the graphs G1 through G4.
transitive closure of G
40
If there are three elements x, y, z ∈ A such that (x, y) ∈ R, (y, z) ∈ R and (x, z) ∉ R, then add blank.
(x, z) to R
41
To find the blank start with the pairs in R and add pairs until you cannot add any more pairs.
transitive closure of relation R,
42
According to the blank, given a directed graph, G and any two vertices in G (u and v) then there is an edge from u to v in Gk if and only if there is a walk of length k from u to v in G.
graph power theorem
43
In a directed graph, the number of lengths of walks from one vertex to another is the blank.
graph power
44
blank is the number of times (length of walks) a relation is composed with itself. For example, if it takes 2 walks to get from a to c, by a to b and b to c, then it is graph power 2. When a relation is composed with itself, then the resulting relation must contain pairs from the original G with a walk length of 2 in order to be valid. If the same relation is composed yet again - a third time - the resulting relation would contain only pairs whose walks in G are length 3. This pattern continues. The number of times (length of walks) a relation is composed with itself is known as the power of the relation.
Powers of relations
45
If you create the union of all Gk , then the resulting relation from the union is the blank that is transitive and contains all the pairs from G. This is referred to as the transitive closure of G and is denoted as G+ .
smallest relation
46
An n × m blank over a set S is an array of elements from S with n rows and m columns.
matrix
47
Each element in a blank is called an entry.
matrix
48
A matrix is called a blank if the number of rows is equal to the number of columns.
square matrix
49
A directed graph G with n vertices can be represented by an n × n matrix over the set {0, 1} called the blank for G. If matrix A is the adjacency matrix for a graph G, then Ai,j = 1 if there is an edge from vertex i to vertex j in G. Otherwise, Ai,j = 0.
adjacency matrix
50
If mathematical operations, such as addition and multiplication, are defined on a set S, then matrix addition and multiplication can be defined for matrices over the set S. A blank is a matrix whose entries are from the set {0, 1}.
Boolean matrix
51
Each entry of the matrix A × B is computed by taking the dot product of a row of A and a column of B. If A and B are n × n matrices, the blank of row i of A and column j of B is the sum of the product of each entry in row i from A with the corresponding entry in column j from B
dot product
52
If A and B are n × n matrices over the integers, then the blank of A and B, denoted AB or A·B, is another n × n matrix such that (AB)i,j is the result of taking the dot product of row i of matrix A and column j of matrix B.
matrix product
53
Matrix multiplication is associative, meaning that if A, B, and C are all n × n matrices, then A(BC) = (AB)C. However, matrix multiplication is not commutative because there are matrices A and B for which AB ≠ BA. The kth blank A is the product of k copies of A:
power of a matrix
54
f G is a directed graph, then the kth power of G (Gk) represents walks of length k in G. There is an edge from vertex v to vertex w in Gk if and only if there is a walk of length exactly k from v to w in G. Matrix multiplication provides a systematic way of computing Gk. What is it?
Take the adjacency matrix A for graph G.
Compute Ak by repeated matrix multiplication.
The matrix Ak is the adjacency matrix for graph Gk. There is a walk of length k in G from vertex v to vertex w if and only if the entry in row v, column w in Ak is 1.
55
The sum of two matrices A and B is well defined if A and B have the same number of rows and the same number of columns. If A and B are two m × n matrices, then the blank of A and B, denoted A + B, is also an m × n matrix such that (A + B)i,j = Ai,j + Bi,j for all 1 ≤ i ≤ m and 1 ≤ j ≤ n.
matrix sum
56
A relation R on a set A is a blank if it is reflexive, transitive, and anti-symmetric.
partial order
57
The domain along with a partial order defined on it is denoted (A, ⪯) and is called a blank
partially ordered set or poset.
58
The pair (N, ⪯) satisfies the conditions for a partial order how
x evenly divides itself (reflexive)
If x evenly divides y and y evenly divides x, then x = y (anti-symmetric)
If x evenly divides y and y evenly divides z, then x evenly divides z (transitive)
59
Two elements of a partially ordered set, x and y, are said to be blank if x ⪯ y or y ⪯ x.
comparable
60
A partial order is a total order if every two elements in the domain are blank. The partial order (Z, ≤) is an example of a total order.
comparable
61
An element x is a blank element if there is no y ≠ x such that y ⪯ x.
minimal
62
An element x is a blank element if there is no y ≠ x such that x ⪯ y.
maximal
63
A blank, named after the 20th century German mathematician Helmut Hasse, is a useful way to depict a partial order on a finite set. Each element is represented by a labeled point.The idea is to show precedence relationships by placing elements that are greater than others towards the top of the diagram. Some precedence relationships are depicted with lines between elements, but only enough to make the relationship between elements clear. Otherwise, the goal is to not clutter the diagram with unnecessary edges.
Hasse diagram
64
The rules for placement and for connecting segments in a Hasse diagram are what
For any x and y such that x ≠ y:
If x ⪯ y, then make x appear lower in the diagram than y.
If x ⪯ y and there is no z such that x ⪯ z and z ⪯ y, then draw a segment connecting x and y.
65
A blank acts similar to the ≤ operator on the elements of its domain
partial order
66
A blank acts similar to the < operator on the elements of its domain
strict order
67
A relation R is a blank if R is transitive and anti-reflexive. The notation a ≺ b is used to express aRb and is read "a is less than b". The difference between the ≺ and the < symbols is the slight curve in the ≺ symbol. The domain along with the strict order defined on it is called a strictly ordered set and is denoted by (A, ≺).
strict order
68
The arrow diagram for a strict order is basically an arrow diagram for a partial order without the blank
self loops
69
The definitions for a partial order carry over in a natural way to strict orders. Two elements, x and y, are said to be blank if x ≺ y or y ≺ x.
comparable
70
A strict order is a blank if every pair of elements is comparable.
total order
71
An element x is a blank if there is no y such that y ≺ x. An element x is a blank if there is no y such that x ≺ y.
minimal element
maximal element
72
Strict orders are blank
anti-symmetric
73
Relations with strict order have the transitive and anti-symmetry properties, but they are not blank.
reflexive
74
The symbol used to show a blank relation is ≺. The domain is denoted by (A, ≺).
strict order
75
The definitions for strict order are very similar to partial order relations. The main difference is the blank (or equality) being removed for strict order.
reflexive
76
A blank (or DAG for short) is a directed graph that has no positive length cycles.
directed acyclic graph
77
DAGs are particularly useful for representing blank relationships.
precedence
78
Let G be a directed graph. G has no positive length cycles if and only if G+ is a blankj.
strict order
79
If a DAG G is transitive, then G+ = G. Thus, the theorem above implies that a directed graph G is a strict order if and only if G is blank and blank.
acyclic and transitive
80
A blank for a DAG is an ordering of the vertices that is consistent with the edges in the graph.
topological sort
81
A relation R is an blank if R is reflexive, symmetric, and transitive.
equivalence relation
82
If a relation R is an equivalence relation, the notation blank is used to express aRb. Blank is read "a is equivalent to b".
a~b
83
If A is the domain of an equivalence relation and a ∈ A, then [a] is defined to be the set of all x ∈ A such that a~x. The set [a] is called an blank
equivalence class.
84
what is the Structure of equivalence relations.
Consider an equivalence relation on a set A. Let x,y ∈ A:
If x~y then [x] = [y]
If it is not the case that x~y, then [x] ∩ [y] = ∅
85
A blank of a set A is a set of non-empty subsets of A that are pairwise disjoint and whose union is A.
partition
86
Equivalence classes are intimately related to blank and, in fact, define each other. An equivalence relation between equivalence classes defines a blank. Likewise, a blank defines an equivalence relation between equivalence classes.
partitions
87
A set of sets is blank if the intersection of any pair of the sets is empty.
pairwise disjoint
88
Pairwise disjoint sets have no blank of any of the sets.
intersection
89
An equivalence relation has what three properties: blank, blank, and blank. An equivalence relation, R, is denoted as a ~ b for aRb.
symmetry, reflexive, and transitive.
90
An equivalence relation is easy to spot when shown as a directed graph: each vertex has a blank.
self- loop
91
An blank is denoted by [a] and is defined to be the set of all x ∈ A such that a ~ x, given A is the domain of an equivalence relation and a is also an element of A. The example of the set of natural numbers, which all have the same remainder when divided by 3, would have classes of [0], [1], and [2].
equivalence class
92
According to the structure of equivalence relations theorem, two equivalence classes are either blank or blank
identical or completely different (disjoint).
93
The set of all distinct equivalence classes of set A is called a blank of the set A. The "distinct" qualification just means a class is only included once if there are two equal equivalence classes.
partition
94
The blank chooses n-tuples from a relational database that satisfy particular conditions on their attributes.
selection operation
95
The blank takes a subset of the attributes and deletes all the other attributes in each of the n-tuples.
projection operation
96
A blank is an attribute (or set of attributes) which provides a unique identity for each n-tuple in the database.
key
