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

Писмени испит из предмета Дискретна математика За смерове Л, М, Н, Р.

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

1

10 поена
  1. Да ли су следећи графови изоморфни?
  2. Да ли су ови графови Ојлерови/Хамилтонови?

2

10 поена

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

3

10 поена

Да ли је следећи граф планаран?

4

10 поена

У бипартитном графу \(G=(V,E),\,V=V_1\sqcup V_2\) класа партиције \(V_1\) садржи \(2017\) чворова и сви чворови ове партиције су степена највише \(10.\) Ако међу свака три чвора из \(V_1\) постоје два чвора који имају заједничког суседа, показати да у \(V_2\) постоји чвор степена бар \(102.\)

5

10 поена
  1. Колико има различитих савршених упаривања комплетног графа са \(n\) чворова?
  2. Показати да свако стабло има највише једно савршено упаривање.