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

ТЕОРИЯ ГРАФОВ

1. Дана симметричная матрица Q смежности. Нарисовать на плоскости мультиграф G=(V,E) (единственный с точностью до изоморфизма), имеющий заданную матрицу Q своей матрицей смежности. Найти матрицу инцидентности ( ) графа G.

Для создания мультиграфа G=(V,E) с заданной матрицей смежности Q на плоскости, нужно выполнить следующие шаги:
1. Создайте вершины графа G, соответствующие строкам и столбцам матрицы Q. Таким образом, количество вершин будет равно размеру матрицы Q.
2. Постройте ребра графа G, соответствующие ненулевым элементам матрицы Q. Для каждого ненулевого элемента q_ij матрицы Q, добавьте ребро между вершинами i и j. Если в матрице Q значение q_ij больше единицы, то добавьте несколько параллельных ребер между вершинами i и j в соответствии с этим значением.
3. Матрица инцидентности ( ) графа G будет иметь размерность "количество вершин" на "количество ребер". Для каждого ребра e_k, найдите индексы вершин, которые это ребро соединяет (назовем их i и j). Затем в матрице инцидентности в позиции (i, k) и (j, k) установите значение 1, а все остальные элементы в этом столбце установите в 0.
4. Если в матрице смежности Q есть петли (то есть q_ii ≠ 0), добавьте соответствующие ребра в граф G и установите соответствующие значения в матрице инцидентности.
В результате этих шагов вы получите мультиграф G с заданной матрицей смежности Q на плоскости, а также матрицу инцидентности ( ) для этого графа.