Образец билета экзамена

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № …

по курсу «Дискретная математика», часть 2 МП-П

I

1. Какой граф называется обыкновенным? Представьте диаграммами все (с точностью до изоморфизма) обыкновенные графы с четырьмя вершинами.

2. Что такое цикломатическое число графа. Найдите цикломатическое число полного графа с пятью вершинами (графа ).

3. Какой граф называется лесом? Приведите пример графа, который является лесом, а также пример графа, который лесом не является.

4. Какой граф называют планарным? Приведите пример полного планарного графа и пример полного графа, который планарным не является.

5. Что можно сказать о хроматическом числе ненулевого обыкновенного графа, не имеющего циклов нечетной длины? Приведите пример такого графа, укажите его хроматическое число.

6. Что такое поток в сети. Что называют величиной потока? Изобразите произвольную сеть с одним источником и одним стоком, задайте на этой сети какой-нибудь поток, укажите величину этого потока.

II

Сформулируйте и докажите теорему о характеристических свойствах деревьев.