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