ВТОРИ ТЕСТ ТЕОРИЯ ПО ДИСКРЕТНИ СТРУКТУРИ 1
			спец . Софтуерно инженерство
				       20.1.2012 г.
Дайте дефиниция на:
1. (20 точки) Краен мултиграф;
2. (20 точки) Маршрут в краен мултиграф
3. (10 точки) Матрица на съседство;
4. (10 точки) Дърво чрез граф;
5. (10 точки) Височина на кореново дърво;
6. (10 точки) Ойлеров граф;
7. (20 точки) Монотонна булева функция и подходяща наредба за тази дефиниция;
Формулирайте:
1. (10 точки) Принципа на умножението;
2. (20 точки) Принцип за включване и изключване за n=3(без да използвате знака за  , а само + и -);
3. (20 точки) Теорема за броя на маршрутите между два връха чрез матрицата на съседство;
4. (30 точки) Алгоритъм за намиране на покривно дърво в ширина за свързан граф;
5. (20 точки) Критерий за пълнота на Пост за множество от булеви функции;