|
|
Матричное задание графов
Для обработки на ЭВМ графы удобно задавать с помощью матриц.
Матрица смежности X для графа G=(V,E) – квадратная матрица размерности |V|:
 ,  .
Свойства матрицы смежности для графа:
- симметрическая матрица;
- столбец и строка, соответствующие изолированной вершине, нулевые;
- элементы главной диагонали равны нулю;
- сумма элементов строки (столбца) матрицы равна степени вершины.
Матрица смежности X для простого псевдографа G=(V,E) – квадратная матрица размерности |V|:
 ,  .
Свойства матрицы смежности для простого псевдографа:
- симметрическая матрица;
- в столбце и строке, соответствующие изолированной вершине, все элементы, кроме элемента главной диагонали, принимают нулевое значение;
- ненулевые элементы главной диагонали соответствуют петле.
Матрица стоимости W для графа G=(V,E) – квадратная матрица размерности |V|:
 , .
Матрица инциденций Z для графа G=(V,E) - матрица размерности |V|x|E|:
 ,  .
Свойство матрицы инциденций для графа:
- нулевая строка соответствует изолированной вершине.
Матрица инциденций Z для простого псевдографа G=(V,E) - матрица размерности |V|x|E|:
 , .
Свойство матрицы инциденций для простого псевдографа:
- нулевая строка соответствует изолированной вершине;
- нулевой столбец соответствует петле.
Матрица смежности X для орграфа G=(V,E) – квадратная матрица размерности |V|:
 , .
Свойства матрицы смежности для орграфа:
- в общем случае несимметрическая матрица;
- столбец и строка, соответствующие изолированной вершине, нулевые;
- элементы главной диагонали равны нулю;
- сумма элементов строки матрицы равна полустепени исхода вершины;
- сумма элементов столбца матрицы равна полустепени захода вершины;
- столбец, соответствующий источнику, нулевой;
- строка, соответствующая стоку, нулевая.
Матрица смежности X для простого псевдоорграфа G=(V,E) – квадратная матрица размерности |V|:
 , .
Свойства матрицы смежности для простого псевдоорграфа:
- в общем случае несимметрическая матрица;
- в столбце и строке, соответствующих изолированной вершине, все элементы, кроме элемента главной диагонали, должны принимать нулевое значение;
- ненулевые элементы главной диагонали соответствуют петле;
- в столбце, соответствующему источнику, все элементы, кроме элемента главной диагонали, должны принимать нулевое значение;
- в строке, соответствующей стоку, все элементы, кроме элемента главной диагонали, должны принимать нулевое значение.
Матрица стоимости W для орграфа G=(V,E) – квадратная матрица размерности |V|:
 , .
Матрица инциденций Z для орграфа G=(V,E) - матрица размерности |V|x|E|:
 , .
Свойство матрицы инциденций для орграфа:
- нулевая строка соответствует изолированной вершине.
Матрица инциденций Z для простого псевдоорграфа G=(V,E) - матрица размерности |V|x|E|:
 , .
Свойство матрицы инциденций для простого псевдоорграфа:
- нулевая строка соответствует изолированной вершине;
- нулевой столбец соответствует петле.
|
|
