Summary SVT Discrete Structures

Discrete Structures
Samenvatting 2017-2018
Quartiel 2




1

,Contents
Introduction............................................................................................................................. 3
Proving.................................................................................................................................... 4
Sets, functions and relations...................................................................................................5
Orderings................................................................................................................................ 7
Counting I................................................................................................................................ 8
Counting II............................................................................................................................... 9
Graphs I................................................................................................................................ 10
Graphs II............................................................................................................................... 11
Trees..................................................................................................................................... 14
Trees/Directed graphs........................................................................................................... 15
Planar graphs........................................................................................................................ 17
Planar graphs II and double counting....................................................................................19
Probability............................................................................................................................. 20
Number theory...................................................................................................................... 22




2

,Introduction
Direct proof
- Most basic approach
- The default approach
- Combine facts (forward) and simplify (backward)

Proof by case distinction
- Useful when there are a small number of configurations
- Prove the statement holds for each possible configuration
- Prove these are all possible configurations




3

,Proving
Proof by contradiction
- Useful when the negation has a ‘there exists’ quantifier
- Assume the negation and show that this is impossible
- Ensure the assumption is the only thing that could be wrong

Pigeonhole principle
If n items are put into m containers and n > m, then there must exist a container that contains
more than one item.

For the sake of contradiction, assume that every container contains at most one item. Let Ci
be the number of items in container i for 1 ≤ i m(so Ci ≤ 1 for all i) then
m m
n=∑ C i ≤ ∑ 1=m<n
i=1 i=1
This is a contradiction with the requirements. Our assumption must be wrong. So there does
exist a container that contains more than one item.

Proof by induction
- Useful if you need to prove infinitely many cases
- Prove one (or more) simple base cases explicitly
- Prove that if the claim holds for k, then it also holds for k + 1

Proof by strong induction
- Useful if you need to prove infinitely many cases
- Prove one (or more) simple base cases explicitly
- Prove that if the claim holds for all values k’ with 1 ≤ k’ ≤ k, then it also holds for k + 1




4

,Sets, functions and relations
Cartesian product
For two sets X and Y, we define their Cartesian product X x Y as
X x Y = {(x, y) | x ∈ X, y ∈ Y}
That is: X x Y is the set of all ordered pairs with the first element in X and the second element
in Y.

Function (or mapping)
Function from set X to set Y is a set of ordered pairs (x, y) with x ∈ X and y ∈ Y, with the
property that for each x ∈ X there is exactly one pair in f whose first component is x.
- If (x, y) ∈ f, we write f(x) = y
- We say f maps x to y, and y is the image of x (under f)

Functions are sometimes called mapping or just map
For a function f: X > Y;
- X is the domain of f
- Y is the range of f
- For A ⊆ X the set f(A) = { f(x): x ∈ A} is the image of A
(under f)
- f(X) is the image of f

Composition of Functions
f: X > Y and g: Y > Z functions
define h: X > Z via h(x) = g(f(x)) for each x ∈ X
- h is a function
- write h = g ∘ f
- composition of functions is associative: a ∘ (b ∘ c) = (a ∘ b) ∘ c
- but not commutative: f ∘ g may even be undefined

Important special types of functions
A function f: X > Y is called
- injective if x ≠ y implies f ( x ) ≠ f ( y )
- surjective, if for every y ∈ Y there exists x ∈ X with f(x) = y
- bijective function, or bijection, if f is injective and surjective

Inverse function
Assume f: X > Y is a bijection
Can define function g: Y > X
- set g(y) = x
- x is the unique element of X with f(x) = y
Note: x exists since f is surjective, it is unique because f is injective
- g is the inverse function of f
- it is commonly denoted by f −1




5

, Relation
A relation between two sets X and Y is a subset R ⊆ X ×Y of the Cartesian producht
Important special case X = Y
- we then speak of a relation on X
- this is an arbitrary subset R ⊆ X × X
For (x, y) ∈ R :
- say: x and y are related
- write xRy

Concatenation of relations
Let X, Y, Z, be sets, let R ⊆ X ×Y be a relation between X and Y, and let S ⊆Y × Z be a
relation between Y and Z
The concatenation of R and S is the following relation T ⊆ X × Z : For x ∈ X and z ∈ Z : xTz if
and only if there exists a y ∈Y with xRy and ySz .

Properties of relations
A relation R on a set X is
- Reflexive, if xRx for all x ∈ X
- Irreflexive, if there is no x ∈ X with xRx
- Symmetric, if xRy implies yRx for all x, y ∈ X
- Antisymmetric if xRy and yRx implies x = y
- Transitive if xRy and yRz implies xRz for all x, y, z ∈ X

Equivalence relation
A relation R on a set X is an equivalence relation if it is reflexive, symmetric and transitive.




6