25.08.2019.
Писмени испит из предмета Дискретна математика
Време израде: 180 минута.
1
10 поена
Испитати да ли следећи бипартитивни графови имају савршено упаривање. Уколико савршено упаривање не постоји, наћи максимално упаривање.
2
10 поена
Одредити хроматски број и хроматски индекс следећих графова:
3
10 поена
Испитати да ли су следећи графови планарни:
4
10 поена
- Ако је \(G\) повезан граф са \(n\) чворова показати да \(G\) садржи подграф \(T\) који је стабло и има \(n\) чворова
- Доказати да повезан граф са \(n\) чворова и \(n\) грана има циклус.
- Нека је \(G\) повезан граф са \(n \ge 4\) чворова и \(m\) грана. Ако је \(m\ge 2n-2\) показати да граф \(G\) има два циклуса исте дужине.
5
10 поена
Нека је граф \(G\) 2-повезан и \(v\in V(G)\) произвољан чвор. Доказати да постоји чвор \(u\in V(G)\) такав да је \(G\setminus\{u,v\}\) повезан.