2.2 Решение заданий 1.7-1.13

Задание: По заданной матрице весов графа G (см. таблицу 1) выполнить:

1. Преобразовать полученный орграф в неориентированный граф.

2. Построить неориентированный граф.

3. Перечислить смежные вершины и ребра,

4. Составить для него матрицу смежности.

5. Указать степени вершин графа.

6. Составить матрицу Кирхгофа и матрицу инцидентности.

7. Изменить граф таким образом, чтобы получить: полный граф, мультиграф, псевдограф, дерево. Построить полученные графы.

1) неориентированный графа G^* получаем из ориентированного графа G заменяя дуги ребрами.

2)Рисунок 6

3)смежные вершины:

v₁v_{2 ;} v₁v_{3 ;} v₁v_{4 ;} v₁v_{5 ;} v₂v_{3 ;} v₃v_{6 ;} v₄v_{2 ;} v₄v_{3 ;} v₄v_{5 ;} v₅v_{2 ;} v₅v_{3 ;} v₅v₆

смежные ребра:

e₁e₂ ; e₁e₃ ; e₁e₄ ; e₁e₅ ; e₁e₉ ; e₁e₁₁ ; e₂e₉ ; e₂e₁₁ ; e₂e₃ ; e₂e₆ ; e₂e₁₂ ; e₂e₁₀ ; e₃e₄

e₃e₅ ; e₃e₆ ; e₃e₁₀ ; e₃e₁₂ ; e₄e₅ ; e₄e₉ ; e₄e₈ ; e₄e₁₀ ; e₅e₈ ; e₅e₁₁ ; e₅e₇ ; e₅e₁₂ ; e₆e₁₀

e₆e₁₂ ; e₆e₇ ; e₇e₈ ; e₇e₁₀ ; e₇e₁₂ ; e₈e₉ ; e₈e₁₀ ; e₈e₁₁ ; e₈e₁₂ ; e₉e₁₀ ; e₉e₁₁ ; e₁₀e₁₂

e₁₁e₁₂

4) Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) -- это квадратная матрица A размера n, в которой значение элемента a_ij равно числу ребёр из i-й вершины графа в j-ю вершину.

5) Степени вершин графа G

Degv₁=4

Degv₂=4

Degv₃=5

Degv₄=4

Degv₅=5

Degv₆=2

6) Дан простой граф G с вершинами V(G)=n. Тогда матрица Кирхгофа данного графа будет определяться следующим образом:

Матрица инцидентности -- одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки -- вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).

В случае ориентированного графа каждому ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".

7) полный граф - рисунок 7, мультиграф - рисунок 8, псевдограф - рисунок 9, дерево - рисунок 10