Лаба 1 по дискретной математике, вар 21 (ТУСУР)

Задание Задание 1. По матрицам (рис. 2; 3) построить диаграммы графов, определив предварительно вид данных матриц. Задание 2. Методами поиска «в глубину» и «в ширину» выделить в графе (рис. 1) между его вершинами наибольший минимальный маршрут. Задание 3. Для каждой пары вершин графа (рис. 1) аналитическим способом вычислить количество маршрутов длины, равной 4, и выделить те пары вершин, для которых их количество ≥ 3, но не более 10. Выписать эти маршруты для какой-либо из выделенных пар. В описании маршрутов указывать вершины и рёбра, входящие в него. Задание 4. Построить матрицу метрики графа (рис. 1). Задание 5. С помощью алгоритма Магу—Вейсмана выполнить правильную раскраску вершин графа с минимальным количеством цветов. Задание 6. Определить число вершинного покрытия графа (рис. 1). Задание 7. Определить содержит ли граф (рис. 1) эйлерову цепь или эйлеров цикл? Ответ обосновать. Задание 8. Аналитическим способом определить число компонент связности графа