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

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

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

1

10 поена

Испитати да ли следећи бипартитивни графови имају савршено упаривање. Уколико савршено упаривање не постоји, наћи максимално упаривање.

2

10 поена

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

3

10 поена

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

4

10 поена
  1. Ако је \(G\) повезан граф са \(n\) чворова показати да \(G\) садржи подграф \(T\) који је стабло и има \(n\) чворова
  2. Доказати да повезан граф са \(n\) чворова и \(n\) грана има циклус.
  3. Нека је \(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\}\) повезан.