Навигация
Граф и его матрица смежности
28460
знаков
7
таблиц
5
изображений
2.2.1 Граф и его матрица смежности
Матрица смежности симметрична относительно главной диагонали (рис. 2.2.1).
2. Матрица инцидентности вершин и рёбер содержит m – строк и n – столбцов, где m – количество вершин, n – количество рёбер.
Рис.1
| a | b | c | d | e | |
| A | 0 | 1 | 1 | 0 | 0 |
| B | 1 | 0 | 0 | 1 | 1 |
| C | 0 | 0 | 1 | 0 | 1 |
| D | 0 | 1 | 0 | 1 | 0 |
| E | 1 | 0 | 0 | 0 | 0 |
| F | 0 | 0 | 0 | 0 | 0 |
Рис 2.2.2 Граф и его матрица инцидентности
В любом столбце матрицы инцидентности (рис. 2.2.2) лиши две единички.
Другой способ представления графа обеспечивает функция, которая выдает списки узлов, с которыми данный узел связан непосредственно. Для графа, отображенного на рис. 2.2.3, такое описание можно представить в виде структуры (таблица 2.1). В колонке s представлены номера узлов, далее в строке таблицы следует список соседних узлов. По этой причине число колонок в каждой из строк различно.
Таблица 2.1
2.3 Представление ориентированных граф
Представление ориентированных граф элементами матриц смежности и инцидентности являются 0, 1, -1. Пусть даны два ориентированных графа (рис. 2.3.1), тогда матрицы смежности и инцидентности для них будут выглядеть как в таблицe 2.3
Рис. 2.3.1 Ориентированные графы
Таблица 2.3
| Матрица смежности | |||||||||||||||||||||||||||||||||
| A | B | ||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||
| Матрица инцидентности | |||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||
В матрице инцидентности для ориентированных граф ставится 0 – если вершина и ребро не инцидентны, -1 – если вершина является началом, 1 – если вершина является концом.
Похожие работы
... , "базовые" алгоритмы: поиск путей, определение компонент связности графа и т.д. 8. Ввод/вывод графов Одной из проблем при создании средств работы с помеченными графами является выбор внешнего файлового формата для хранения графов. До недавнего времени каждая программная система использовала свой собственный, уникальный формат, что приводило к сложностям при организации обмена данными. ...
... write(fileKlics,klika); end; end; end; {конец пеpебоpа возможных мест в стpоке} end; {конец пpохода по стpокам} close(fileklics); end; Выше представлена процедура нахождения клик в графе. Описание переменных: StolbecSravn: номер сравниваемого столбца. StringSravn: номер текущей строки. Num ,i1,i: счетчики. lenStolb: размер множества вершин клики. Stolbec: номер столбца первой ...
... . Вся процедура поиска представлена ниже (данная процедура используется также и для просмотра графа, и в псевдокоде, описанном ниже, отсутствуют операторы, которые не используются для поиска). 1 procedure WS (v); (*поиск в ширину в графе с началом в вершине v; переменные НОВЫЙ, ЗАПИСЬ — глобальные *) 2 begin 3 ОЧЕРЕДЬ := Æ; ОЧЕРЕДЬ <= v; НОВЫЙ [v] := ложь 4 while ОЧЕРЕДЬ &# ...
... файла из которого будет происходить ввод X – грав в последовательном представлении O(N,N1)=N2 N2 – количество вершин в графе X Текст программы. # include # include # include # include # include # include /////////////////////////////////////////////////////////////////////////////////////////////////////// struct Spisok //Связанное представление графа { int index; //Содержвтельная " ...
0 комментариев