МАТФ РОКОВИ
05.06.2019.

Писмени испит из предмета Дискретна математика

Време израде: 180 минута.

1

10 поена

Испитати који од следећих графова су изоморфни:

2

10 поена

Да ли су следећи графови Ојлерови/Хамилтонови?

3

10 поена

Испитати да ли су следећи графови планарни:

4

10 поена

Показати да се гране \(k\)-регуларног бипартитног графа могу партиционисати на \(k\) дисјунктних савршених упаривања.

5

10 поена

Нека је \(T\) дрво чији чворови имају степен \(1\) или \(3.\)

  1. Ако \(T\) има бар \(n\) листова, показати да \(T\) има \(n-2\) чвора степена \(3.\)
  2. Ако \(T\) има бар \(4\) листа, показати да постоји чвор који је суседан са два листа.