离散数学

Chapter-8

Inclusion-Exclusion

Let $A_1,A_2,\cdots A_n$ be finite sets, then

$$\begin{align} |A_1\cup A_2\cup\cdots\cup A_n| &=\sum_{1\leq i\leq n}|A_i| -\sum_{1\leq i< j\leq n}|A_i\cap A_j|\\ &+\sum_{1\leq i<j<k\leq n}|A_i\cap A_j\cap A_k|-\cdots+(-1)^{n+1}|A_1\cap A_2\cap\cdots\cap A_n| \end{align}$$

Chapter-9 Relations

A binary relation from $A$ to $B$ is a subset of $A\times B$
A relation on a set $A$ is a relation from $A$ to $A$

Reflexive $\forall a\in A,(a,a)\in R$
symmetric $\forall a,b\in A,(a,b)\in R\rightarrow (b,a)\in R$
antisymmetric $\forall a,b\in A,((a,b)\in R\land (b,a)\in R)\rightarrow a=b$
transitive $\forall a,b,c\in A,((a,b)\in R\land(b,c)\in R)\rightarrow (a,c)\in R$
composite $(\exists b\in B((a,b)\in R\land(b,c)\in S))\rightarrow (a,c)\in S\circ R$

The relation $R$ on a set $A$ is transitive if and only if $R^n\subseteq R$ for $n=1,2,3\cdots$

An n-ary relation is a subset of $A_1\times A_2\times\cdots\times A_n$
The sets $A_1,A_2,\cdots,A_n$ are called the domains of the relation
$n$ is called its degree
A domain is a primary key when no two n-tuples in the relation have the same value

$R$ is symmetric if and only if $M_R=(M_R)^t$
$M_{R_1\cup R_2}=M_{R_1}\lor M_{R_2}$
$M_{R_1\cap R_2}=M_{R_1}\land M_{R_2}$
$M_{S\circ R}=M_R\odot M_S$

an edge of the form $(a,a)$ is called a loop

the closure of $R$ with respect to $P$ is the relation $S$ on $A$ with property $P$ that contains $R$ and is a subset of every subset containing $R$ with property $P$

There is a path of length $n$ from $a$ to $b$ if and only if $(a,b)\in R^n$

The connectivity relation $R^$ consists of the pairs $(a,b)$ such that there is a path of length at least one from $a$ to $b$ in $R$ , $\begin{align}R^=\bigcup_{n=1}^\infty R^n\end{align}$

$M_{R^*}=M_R\lor M_R^{[2]}\lor M_R^{[3]}\lor\cdots\lor M_R^{[n]}$

$W_k=[w_{ij}^{[k]}],\quad w_{ij}^{[k]}=w_{ij}^{[k-1]}\lor(w_{ik}^{[k-1]}\land w_{kj}^{[k-1]})$

Equivalence relation is reflexive, symmetric and transitive

Two elements $a$ and $b$ that are related by an equivalence relation are called equivalent. $a\sim b$ denote that $a$ and $b$ are equivalent elements with respect to a particular equivalence relation

Let $R$ be a 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$
$[a]_R=\{s|(a,s)\in R\}$
If $b\in[a]_R$ , then $b$ is called a representative of this equivalence class

Let $R$ be an equivalence relation on a set $A$. these statements for elements $a$ and $b$ of $A$ are equivalent: $aRb,\quad [a]=[b],\quad [a]\cap[b]\neq\emptyset$

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\in I\}$ of the set $S$ , there is an equivalence relation $R$ that has the sets $A_i,i\in I$ as its equivalence classes.

A relation $R$ on $S$ is called a partial ordering if it is reflexive, antisymmetric and transitive. A set $S$ together with a partial ordering $R$ is called a partially ordered set, and is denoted by $(S,R)$ . Members of $S$ are called elements of the poset.

The elements $a$ and $b$ of a poset $(S,\preceq)$ are called comparable if either $a\preceq b$ or $b\preceq a$ . When $a$ and $b$ are elements of $S$ such that neither $a\preceq b$ nor $b\preceq a$ , $a$ and $b$ are called incomparable.

If $(S,\preceq)$ is a poset and every two elements of $S$ are comparable , $S$ is called a totally ordered or linearly ordered set, and $\preceq$ is called a total order or a linear order. A totally ordered set is also called a chain.

$(S,\preceq)$ is a well-ordered set if it is a poset such that $\preceq$ is a total ordering and every nonempty subset of $S$ has a least element.

Suppose that $S$ is a well-ordered set. Then $P(x)$ is true for all $x\in S$
For every $y\in S$, if $P(x)$ is true for all $x\in S$ with $x\prec y$ , then $P(y)$ is true

An element of a poset is called maximal if it is not less than any element of the poset
An element of a poset is called minimal if it is not greater than any element of the poset

greatest element is an element in a poset that is greater than every other element
least element is an element in a poset that is less than every other element

upper bound /lower bound /least upper bound /greatest lower bound

A partially ordered set in which every pair of elements has both a least upper bound and a greatest lower bound is called a lattice

Every finite nonempty poset $(S,\preceq)$ has at least one minimal element

Chapter-10 Graphs

Graphs and Graph Models

A graph $G=(V,E)$ consists of $V$ ,a nonempty set of vertices (or nodes) and $E$ ,a set of edges. Each edge has either $1$ or $2$ vertices associated with it , called its endpoints.

A digraph $(V, E)$ consists of a nonempty set of vertices $V$ and a set of directed edges $E$. Each directed edge is associated with an ordered pair of vertices. The directed edge $(u, v)$ is said to start at $u$ and end at $v$.

The set of all neighbors of a vertex $v$ of $G=(V,E)$ , denoted by $N(v)$ , is called the neighborhood of $v$ . If $A$ is a subset of $V$ , we denote by $N(A)$ the set of all vertices in $G$ that are adjacent to at least one vertex in $A$ , $N(A)=\bigcup_{c\in A}N(v)$

The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. The degree of the vertex v is denoted by $\deg(v)$

Let $G=(V,E)$ be an undirected graph with $m$ edges, then

$$2m=\sum_{v\in V}\deg(v)$$

An undirected graph has an even number of vertices of odd degree.

In a graph with directed edges the in-degree of a vertex $v$, denoted by $\deg^−(v)$, is the number of edges with $v$ as their terminal vertex. The out-degree of $v$, denoted by $deg^+(v)$, is the number of edges with $v$ as their initial vertex.

Let $G=(V,E)$ be a graph with directed edges, then

$$\sum_{v\in V}\deg^-(v)=\sum_{v\in V}\deg^+(v)=|E|$$

Bipartite Graphs

A simple graph $G$ is called bipartite if its vertex set $V$ can be partitioned into two disjoint set $V_1$ and $V_2$ such that every edge in the graph connects a vertex in $V_1$ and a vertex in $V_2$ , the pair $(V_1,V_2)$ is a bipartition of the vertex set $V$ of $G$

A simple graph is bipartite if and only if it is possible to assign one of two different colors to each vertex of the graph so that no two adjacent vertices are assigned the same color.

A matching $M$ in a simple graph $G=(V,E)$ is a subset of the set $E$ of edges of the graph such that no two edges are incident with the same vertex.

A matching $M$ in a bipartite graph $G=(V,E)$ with bipartition $(V_1,V_2)$ is a complete matching from $V_1$ to $V_2$ if every vertex in $V_1$ is the endpoint of an edge in the matching, equivalently $|M|=|V_1|$

The bipartite graph $G=(V,E)$ with bipartition $(V_1,V_2)$ has complete matching from $V_1$ to $V_2$ if and only if $|N(A)|\geq|A|$ for all subsets $A$ of $V_1$

A subgraph of a graph $G=(V,E)$ is a graph $H=(W,F)$ ,where $W\subseteq V$ and $F\subseteq E$
A subgraph $H$ of $G$ is a proper subgraph of $G$ if $H\neq G$

Let $G=(V,E)$ be a simple graph, the subgraph induce by a subset $W$ of the vertex set $V$ is the graph $(W,F)$ , where the edges set $F$ contains an edge in $E$ if and only if both endpoints of this edge are in $W$

Representing Graphs