06.06.2017.

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

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

1

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

2

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

3

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

4

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

5

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