Вопрос №37 Кольцо многочленов.
В общей алгебре, кольцо многочленов — это кольцо, образованное многочленами от одной или нескольких переменных с коэффициентами из другого кольца. Изучение свойств колец многочленов оказало большое влияние на многие области современной математики; можно привести примеры теоремы Гильберта о базисе, конструкции поля разложения и изучения свойств линейных операторов.
Вопрос №38. Вопрос №39. Графы: простой, мультиграф, псевдограф.
Псевдограф – граф с кратными ребрами и петлями. Пример: пусть D=(V,X) – ориентированный граф, V={V1,V2},X={x1={V1,V2},x2={V1,V2],x3={V1,V2},x4={V2,V2} . Тогда D=(V,X) – ориентированный псевдограф Мультиграф Мультиграф – граф, в котором имеются кратные (параллельные) ребра. Мультиграф – это псевдограф без петель. Пример: пусть D=(V,X) – ориентированный граф,V={V1,V2} ,X={x1={V1,V2},x2={V1,V2}} . Тогда D=(V,X)– ориентированный мультиграф. Простой граф Простые графы — не имеющие петель и кратных рёбер.
Вопрос №40. Маршруты, цепи, циклы. Связность.
Определение 6 (Маршрут). Маршрутом в графе G = <V,E; I> называется последовательность вершин и рёбер вида v0,e1,v1,e2, ..., vn-1,en,vn, где vi О V, i О [0,n], ei О E, (vi-1,ei), (vi,ei) О I, i О [1,n]. Вершины v0, vn называются связанными данным маршрутом (или просто связанными). Вершину v0 называют началом, а vn – концом маршрута. Если v0 = vn, то маршрут называют замкнутым. Число n называется длиной маршрута.
41*. Изоморфизм графов (1). Операции над графами (2). Гомеоморфизм графов (3).
1)
2)
3)
Операция подразбиения (измельчения) дуги (u, v) в орграфе D = (V, E) состоит в удалении из Е дуги (u, v), добавлении к V новой вершины w и добавлении к Е | {(u, v)} двух дуг (u, v), (w, v). Аналогично определяется операция подразбиения ребра в графах.
Определение. Орграф D1 называется подразбиением орграфа D2, если орграф D1 можно получить из D2 путем последовательного применения операции подразбиения дуг. Аналогично определяется подразбиение графа.
Определение. Орграфы D1, D2 называются гомеоморфными, если существуют их подразбиения, являющиеся изоморфными.
42. Представления графов. Матрицы смежности, инцидентности, весов графа (1). Список ребер графа (2).
1)
Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элементаaij равно числу рёбер из i-й вершины графа в j-ю вершину.
Иногда, особенно в случае неориентированного графа, петля (ребро из i-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента aii в этом случае равно удвоенному числу петель вокруг i-й вершины.
Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали.
aij — число рёбер, связывающих вершины Vi и Vj, причем в некоторых приложениях каждая петля (ребро {vi и vj} при некотором i) учитывается дважды.
Матрица смежности пустого графа, не содержащего ни одного ребра, состоит из одних нулей.
Матрица инцидентности
Таблица, где строки соответствуют вершинам графа, а столбцы соответствуют связям (рёбрам) графа. В ячейку матрицы на пересечении строки со столбцом записывается:
1
в случае, если связь j «выходит» из вершины i,
−1,
если связь «входит» в вершину,
0
во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине)
Данный способ является самым ёмким (размер пропорционален |V||E|) для хранения, поэтому применяется очень редко, в особых случаях (например, для быстрого нахождения циклов в графе).