|
 Архив разработки (89 Кб, Mathcad-документ)
Cодержание
- Унарные операции
- Бинарные операции
В данной работе для визуализации графов используется программа Шумилкиной Елены и Смирновой Ольги (см. банк студенческих задач).
В первой части работы реализуются основные унарные операции над графами: дополнение графа относительно полного графа, удаление вершин, отождествление вершин и расщепление вершин.
1. Выполняем генерацию матрицы смежности M(G) неориентированного графа G.
- количество вершин в графе
алгоритм генерации матрицы графа:
При визуализации графов счет вершин ведется по часовой стрелке от левой вершины
2. Вычисляем матрицу дополнения графа G относительно полного графа.
алгоритм вычисления матрицы дополнения графа:
М - матрица графа G, N матрица его дополнение относительно полного графа.
 
3. Вычисляем матрицы подграфов графа G, которые получаются путем удаления из графа одной или нескольких вершин.
aлгоритм удаления из графа вершины:
 |
// для этого удалим
// сначала строку
// затем столбец
|
q - номер удаляемой вершины
удаляем из графа G 4-ю вершину:
 
L - матрица подграфа графа M, М - (сейчас и в дальнейшем) матрица исходного графа
удаляем из графа M 5-ю вершину и 1-ю вершины:
N матрица подграфа графа M.
4. Выполняем операцию отождествеления вершин (стягивания ребра) в графе G.
алгоритм отождествления вершин:
 |
// удаляем из матрицы
// М вторую из
// отождествляемых
// вершин
// удаляем из матрицы
// М столбец
// просматриваем
// строку
// удаляем из матрицы
// М строку
// просматриваем
// столбец
|
x, y - номера отождествляемых вершин
граф после отождествления 4-ой и 5-ой вершин:
исходный граф:
Примечание: программа работает корректно если номер первой отождествляемой вершины меньше второй (x<y), окружение второй вершины складывается с окружением первой вершины и вторая вершина удаляется.
4. Выполняем операцию расщепления вершин графа G.
алгоритм расщепления вершин:
 |
// добавляем новую (n+1 - ю) вершину
// сдвигаем вершины, освобождая
// место для двух вершин
// обнуляем вершину расщепления и
// новую вершину
// разбиваем окружение расщепляемой
// вершины на две произвольные части
// соединяем две новые вершины
// делаем матрицу симметричной
|
x - номер расщепляемой вершины
Примечание: окружение расщепляемой вершины разбивается на две части произвольно; новая вершина добавляется сразу после расщепляемой остальные же сдивагаются по часовой стрелке на рис., т.е. их номер увеличивается на 1, эта деталь значительно усложнила алгоритм, который становится намного проще если новую вершину добавлять сразу за последней вершиной исходного графа.
|
