Как из матрицы построить граф

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

Инструкция

1. Графы бывают ориентированными и неориентированными. В первом случае ребра, соединяющие вершины графа, задают направление движения стрелкой на одном из своих концов. Если ребро начинается и заканчивается в одной и той же вершине, оно вырождается в петлю. Все данные условия графа явно задаются в матрице инцинденций. Матрица смежностей содержит лишь информацию о наличии связи между вершинами графа, не раскрывая ее особенностей.
2. Постройте граф по матрице инцинденций. Для этого посчитайте количество строк n и столбцов m в заданной матрице. Строки соответствуют вершинам графа, а столбцы – ребрам. На свободном пространстве листа отметьте вершины строящегося графа кружками, их будет столько, сколько строк содержит матрица инцинденций. Пронумеруйте вершины от 1 до n.
3. Разбор матрицы лучше осуществлять по столбцам, определяя таким образом наличие связи между вершинами и ее направление. Просматривая первый столбец сверху вниз, ищите значение отличное от нуля. При нахождении числа -1 или 1 запомните, в какой строке оно расположено, и ищите вторую единицу в том же столбце. Обнаружив оба числа, проведите на графе линию, соединяющую две вершины с номерами отмеченных строк. Если одно из найденных значений было -1, значит, граф является ориентированным – укажите на линии направляющую стрелку к той вершине, где в матрице находится -1. Если оба значения описаны единицами, следовательно, строящийся граф неориентированный и его ребра не имеют направления. Если в столбце обнаружено число 2, проведите петлю в вершине, соответствующей позиционной строке матрицы. Нулевые значения указывают на отсутствие связи. Рассмотрите аналогичным образом остальные столбцы и отобразите на рисунке все заданные ребра графа.
4. Постройте граф по матрице смежности. Данная матрица является квадратной, т.к. число ее строк равно числу столбцов и соответствует количеству вершин в графе. На листе нарисуйте кружки-вершины по числу срок матрицы. Разбор матрицы смежности лучше проводить, двигаясь по строке. Начиная с первой строки слева направо, ищите значения отличные от нуля. Найдя 1 (или другое ненулевое число) заметьте его текущую позицию в строке и столбце. На графе проведите линию между вершинами, соответствующими замеченными строке и столбцу. Т.е. если 1 стоит на пересечении 2 строки и 3 столбца матрицы смежности, ребро графа соединит 2 и 3 его вершины. Продолжите поиск ненулевых значений до конца матрицы смежности и заполните граф аналогичным образом.