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

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

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

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

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

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

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

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

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

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

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

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