Задание 8

Отношение f является функцией, т.к. каждому значению x соответствует единственное значение y.

Отношение f не является инъективным, т.к. значению y соответствуют два значения x. Например, y=5, x1=0, x2= -3.

Отношение f не является сюръективным, т.к. не существует x для отрицательных значений y.

Отношение является отображением, т.к. можно рассчитать y для всех x из множества R.

Теория графов

Основные понятия и определения

· Граф – пара множеств V и X - G = (V, X). V – множество вершин, X – множество ребер.

· Петля – ребро вида (v, v).

· Кратные рёбра – одинаковые пары в X.

· Ориентированный граф (орграф D) – граф, для которого пары в Х упорядочены. Ребра в орграфе называются дугами и обозначаются < u, v>.

· Степенью вершины V графа G называется число d(v) рёбер графа, инцидентных вершине v. Если d(v) = 1, тогда v – висячая вершина, если d(v) = 0, тогда v –изолированная вершина.

· Полустепенью исхода (захода) вершины v орграфа D называется d⁺(v) – число дуг, исходящих из v (δ ^- (v)- число дуг, заходящих в v).

· Маршрутом для графа G (путём для орграфа D) называется последовательность v₁x₁v₂x₂v₃...x_kv_k+1.

· Цепь – незамкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны.

· Простая цепь – цепь, в которой все вершины попарно различны.

· Цикл (контур) - замкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны.

· Простой цикл (контур) - цикл (контур), в котором все вершины попарно различны.

· Длина пути – число рёбер (дуг) в маршруте (пути).

· Путь в графе называется минимальным, если он состоит из минимального количества рёбер.

· Орграф D называется нагруженным, если на множестве дуг Х определена весовая функция – длина дуги хÎ Х.

· Путь называется минимальным в нагруженном графе или орграфе, если он имеет минимальную длину пути.

· Матрица смежности (графа, орграфа): А = [a_ij], V = {v₁…, v_n},

· X = {x₁…, x_m}

·

· Матрица инцидентности: B = [b_ij]

· (орграфа D)

·

· (графа G)

·

· Матрица достижимости T = [t_ij]

·

· Матрица связности S = [s_ij]

· (орграфа D)

· (графа G)

· Дерево – связный граф без циклов

· Остовное дерево графа (ОД) – любой связный подграф связного графа, содержащий все вершины и являющийся деревом.

Минимальное остовное дерево (МОД) – остовное дерево нагруженного графа с минимальной суммой длин дуг, содержащихся в нём.

· Цикломатическое число связного графа G (число циклов в базисе циклов графа) , где n – количество вершин, m – количество ребер в графе.