Summary
Summary SVT Discrete Structures
- Course
- Institution
Summary for Discrete Structures
[Show more]
Seller
Follow
ylfrettub
Reviews received
Content preview
Discrete StructuresSamenvatting 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller ylfrettub. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.21. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
52510 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now