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

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

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

1

10 поена

Да ли су следећи графови Ојлерови/Хамилтонови? Уколико јесу наћи Ојлерову шетњу односно Хамилтонов циклус.

2

10 поена

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

3

10 поена

Одредити хроматски број и хроматски индекс следећег графа:

4

10 поена

Нека је \(G\) бипартитивни граф са партицијом \((A,B)\) где је \(\lvert A \rvert =\lvert B\rvert = n.\) Испитати да ли граф \(G\) има савршено упaривање ако садржи најмање \(n^2-\frac{2n}{3}\) грана.

5

10 поена

Нека је \(G\) граф са \(n\) чворова који је изоморфан свом комплементу. Показати да је \(n\equiv 1 \pmod 4\) акко \(G\) садржи чвор степена \(\frac{n-1}{2}.\)