06.06.2017.
Писмени испит из предмета Дискретна математика За смерове Л, М, Н, Р.
Време израде: 180 минута.
1
10 поена
- Да ли су следећи графови изоморфни?
- Да ли су ови графови Ојлерови/Хамилтонови?
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 поена
- Колико има различитих савршених упаривања комплетног графа са \(n\) чворова?
- Показати да свако стабло има највише једно савршено упаривање.