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}.\)