а) Для графа и н- постройте матрицы смежности и матрицы инциденций.
б) Для графа н- проверьте, является ли он эйлеровым. Если нет, то обоснуйте почему. В противном случае постройте и приведите для этого графа эйлеров цикл.
в) Методом Краскала постройте остов (любой) графа .
Примечание к выбору варианта из задач серии 41- 50.
Сформулированные ниже задачи с номерами 41-50 относятся к разделу программы «Теория графов». Соответствующие графы представлены в виде диаграмм G1- G10 ниже.
Номер варианта j серии задач 41- 50 контрольной работы выполняется студентом для граф , который является предметом исследования в сформулированных ниже задачах. Так, если студенту нужно выполнить вариант задачи 43, то он решает эту задачу для графа G3.
Присвойте вершинам графа попарно различные номера из диапазона 1,2,…, n, где n – число вершин графа .
Представленные графы являются ориентированными, но наряду с каждым таким графом рассмотрите неориентированный граф, полученный из него заменой каждой дуги ребром. Последний граф далее в условиях задач обозначается как н- .
|
|