Samenvatting
Summary SVT Discrete Structures
Samenvatting voor Discrete Structures
[Meer zien]Voorbeeld 6 van de 24 pagina's
Voorbeeld 6 van de 24 pagina's
In winkelwagengesponsord bericht van onze partner
Voorbeeld van de inhoud
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
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper ylfrettub. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €2,99. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 52510 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen