![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № …
по курсу «Дискретная математика», часть 2 МП-П
I
1. Какой граф называется обыкновенным? Представьте диаграммами все (с точностью до изоморфизма) обыкновенные графы с четырьмя вершинами.
2. Что такое цикломатическое число графа. Найдите цикломатическое число полного графа с пятью вершинами (графа ).
3. Какой граф называется лесом? Приведите пример графа, который является лесом, а также пример графа, который лесом не является.
4. Какой граф называют планарным? Приведите пример полного планарного графа и пример полного графа, который планарным не является.
5. Что можно сказать о хроматическом числе ненулевого обыкновенного графа, не имеющего циклов нечетной длины? Приведите пример такого графа, укажите его хроматическое число.
6. Что такое поток в сети. Что называют величиной потока? Изобразите произвольную сеть с одним источником и одним стоком, задайте на этой сети какой-нибудь поток, укажите величину этого потока.
II
Сформулируйте и докажите теорему о характеристических свойствах деревьев.
Дата публикования: 2014-11-03; Прочитано: 378 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!