Контрольная работа по дискретной математике

1.    Задать граф следующими способами: перечислением, матрицами смежности и инцидентности.

2.    Определить следующие основные характеристики графа: число ребер и дуг; число вершин; коэффициент связности графа; степени всех вершин; цикломатическое число графа.

3.    Определить, является ли данный граф:

-      планарным или плоским графом (обосновать ответ и выполнить обратное преобразование);

-       двудольным графом (обосновать ответ и, если необходимо, то достроить до двудольного графа);

-      деревом (обосновать ответ и, в случае циклического графа, привести один из вариантов основного дерева);

-       псевдографом или мультиграфом, или простым графом (обосновать ответ и выполнить необходимые преобразования).

4.    Привести пример подграфа, частичного графа и частичного подграфа.

5.    Произвести реберную и вершинную раскраски графа. Определить вершинное и реберное хроматические числа, указать классы и соцветия.

6.    Определить метрические характеристики графа: диаметр, радиус, эксцентриситет каждой вершины, центральные вершины.

7.    Упорядочить граф матричным способом и построить порядковую функцию, функцию Гранди.