Mathematically, relations are subsets of Descartes, namely, two-dimensional tables, matrices and directed graphs.
N-ary relation, multiple (> 2) Cartesian subsets of a set, and the number of sets is called the order of the relation, which is called n. It is similar to the number of n..
Binary relations can be represented by sets, graphs and matrices.
Regarding the relationship in discrete mathematics, the following concepts will appear: binary relationship, equivalent relationship and separable relationship.
We can deeply understand the significance of this relationship by analyzing their sexuality.
In this paper, we mainly discuss three representations of relationships. It will involve undirected graph, adjacency matrix, incidence matrix, equivalence relation and divisibility relation.
Because in binary relations, there are three ways to express relations: set representation, graph representation and matrix representation. In other words, all three ways can explain the relationship. Graphical method includes directed graph and undirected graph, and matrix includes incidence matrix and adjacency matrix.
Number of elements in cardinality (order) set |A|.
For example, let A=( 1, 2,3,4 4) R be a binary relation on a, p {
The relationship matrix is:
1 0 1 0
0 0 0 0
1 0 1 0
1 1 1 0
Set a = {x 1, x2, ..., XM}, b = {y 1, y2, ..., yn}, r is the binary relationship between a and b, take the elements in a and b as vertices, if εR, draw a directed edge from the vertex xi to yj, and draw the graph G.
For example, as shown in figure-1, the relation graph is a graph with vertex {1, 2,3,4} and edge p,
It is clear whether the incidence matrix and adjacency matrix represent graphs in the form of matrices, which still belongs to the category of graph theory.
Incidence matrix refers to the matrix that represents the relationship between each point and each edge. The incidence matrix focuses on whether the vertices are related, and the number of incidence is specific, which is related to the endpoints and starting points of vertices and edges (for directed graphs).
For undirected graph g, pxq, p is the number of vertices and q is the number of edges. B i j represents the relationship between point I and edge j in the incidence matrix. If point I is connected with edge j, b i j = 1. Otherwise, b i j = 0.
Figure-1 means p=4 and q=4.
4*4 matrix diagram, b 1 e 1 indicates whether the fixed point 1 and the edge e 1 are connected, and the connection is 1, otherwise it is 0. The following matrix diagram is obtained in turn.
The matrix diagram is as follows
In fact, the above is the way to express undirected graph with incidence matrix.
Another concept that is similar to incidence matrix but easy to be confused is adjacency matrix. The adjacency matrix represents the relationship between vertices.
The set of vertices is a one-dimensional array, and the relationship between vertices is a two-dimensional array.
The same incidence matrix is represented by two one-dimensional arrays.
As shown in Figure -3, the relationship can be divided
example
Set a set of factors with a value of 54, R A×A, x, y∈A, xRy x divided by Y. Draw a Haas diagram of a poset, and find the largest element, the smallest element, the largest element and the smallest element.
First, we understand what a factor is.
The multiple of x is 54, and x is its factor. For example, 2*27=54, then 2 and 27 are its factors.
A={ 1,2,3,6,9, 18,27,54}
Maximum element, maximum element: 54
Minimum element: 1
Separable relation of discrete mathematics
Separable relation
Adjacency matrix and incidence matrix