1) A and B being a finite set with |A| > |B| and f : A -> B f being a linear mapping. Show that f is not
injective
2) ? ∈ ℕ
- being a positive natural Number. A and B being a finite set with |A| > k |B| and f : A -> B f
being a linear mapping. Prove that there is a ? ∈ ? with |?
−1
({?})| ≥ ? +1
?
−1
: P(B) -> P(A) being the inverse image of f.
3) A being a non empty, finite set. An image f called 2-Colouring of a, if you assign a colour to every
element from A. Show through complete induction that there are 2
|?|
variations of 2-Colouring from
A.
4) A Word with the length ? ∈ ℕ from the Alphabet ∑ := {0, 1} is a
Squence w = (?0
, ?1
, … , ??−1) ∈ ∑
?
. In the case ? =0 it’s the empty word/sequence(). ? ∈ ℕ .
Prove that there are 2
?+1 − 1 Words with a length of maximum n over the Alphabet ∑
5) ? ∈ ℕ, A a finite set with |A|=n and ∑ := {0, 1}. F being the amount of all 2-Colouring from A, and W
the amount of all Words of the length ? over the Alphabet ∑.
Show that there is a Bijection between F and W.
6) G is a connected graph and ? ∈ ℕ is chosen that for all blocks ? ⊆ G applies |?(?)| ≤ ?.
a) State an algorithm (without reasoning) that provides a largest (concerning Cardinality)
independent set in G and it’s runtime is in ?(?(?)?(|?(?)|)).
f being a function described by f: ℕ → ℕ that only depends on k while p: ℕ → ℕ is a
polynomial that only depends on |?(?)|.
b) Prove the correctness of the algorithm from a
c) Justify why the runtime from a is in ?(?(?)?(|?(?)|)).
7) ? ∈ ℕ - a positive natural number. We know one Graph G, that is able to be made c-planar, that if
there is a set ? ⊆ V(G) with maximum of c nodes that: G – S planar.
a) Give an example graph G with a maximum of 10 nodes that can’t be made 2-planar but 3-planar.
Show that your example is correct by selecting a set ? ⊆ V(G) of Cardinality 3 so that G-S
planar.
b) G is a Graph that can be made 5-planar. How many pairwise node-disjoint copies of ?5 can G
contain at a maximum. Provide the best boundaries and reasons for your answer.
c) G is a Graph with ? ∈ ℕ - blocks, all blocks are able to be made into c-planars. How many pairwise
node-disjoint copies of ?5 can G contain at a maximum? State the best boundaries in dependency
to b and c plus your reasoning behind it.
d) G being a graph and B a block from G, prove ?
(?) = ????⊆G?
(?)
8) X is a finite set with n:= |?|. A set ? ⊆ ?(?) is a Clutter, if for all ?,? ∈ ? applies: If ? ⊆ ? then A=B
a) X:={1,2,3,4}. State a Clutter ? ⊆ ?(?) with |?| = (
4
2
)
b) Clutter ? ⊆ ?(?). Show that |?| ≤ (
?
|
?
2
|
)
9) X is a finite set with n:= |?|. A set ? ⊆ ?(?) is a Clutter.
F is simple, if for all ?, ? ∈ ? with ? ≠ ? applies: |? ∩ ?| ≤ 1 and |?| ≥ 2.
F is forestlike, if for all sub-families ? ⊆ ? an ? ∈ ? and an element ? ∈ ? exists, that ? ∈ ?
with ? ≠ ? applies: if ? ∩ ? ≠ 0 then ? ∩ ? = {?}.
C ⊆ ?(?) is a set that is a subset of X. A real 2-colouring of C is a transformation f:X->{red,blue},
so that ? ∈ ? applies ? ∩ ?
−1
({???}) ≠ 0 and ? ∩ ?
−1
({????}) ≠ 0.
a) G is a connected graph with a minimum of 2 nodes. We define the following set:
?(?) ≔ {?(?)|? ⊆ ? and ? is a block from ?} ⊆ ?(?(?))
Prove that B(G) is a simple and forestlike Clutter.
b) Show that there is a real 2-colouring for every simple and forestlike Clutter ? ⊆ ?(?).