05.06.2019.

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

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

1

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

2

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

3

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

4

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

5

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

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