Ранг (теория графов)

Характеристика неориентированных графов

В теории графов , разделе математики, ранг неориентированного графа имеет два не связанных между собой определения. Пусть $n$ равно числу вершин графа.

В матричной теории графов ранг $r$ неориентированного графа определяется как ранг его матрицы смежности .

Аналогично, недействительность графа — это недействительность его матрицы смежности, которая равна

n - r

.

В теории матроидов графов ранг неориентированного графа определяется как число $n - c$ , где $c$ — число связных компонент графа. ^[1] Эквивалентно, ранг графа — это ранг ориентированной матрицы инцидентности, связанной с графом. ^[2]

Аналогично, недействительность графа — это недействительность его ориентированной матрицы инцидентности, заданной формулой

m - n + c

, где n и c такие же, как и выше, а m — количество ребер в графе. Недействительность равна первому числу Бетти графа. Сумма ранга и недействительности — это количество ребер.

Примеры

Пример графика и матрицы:

(соответствующие четырем ребрам, e1–e4):

	1	2	3	4
1	0	1	1	1
2	1	0	0	0
3	1	0	0	1
4	1	0	1	0

=

${\begin{pmatrix}0&1&1&1\\1&0&0&0\\1&0&0&1\\1&0&1&0\\\end{pmatrix}}.$

В этом примере ранг матрицы по теории матриц равен 4, поскольку ее векторы-столбцы линейно независимы.

Смотрите также

Примечания

^ Weisstein, Eric W. "Graph Rank". Из MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GraphRank.html
^ Гроссман, Джерролд В.; Кулкарни, Девадатта М.; Шохетман, Ирвин Э. (1995), «О минорах матрицы инцидентности и ее нормальной форме Смита», Линейная алгебра и ее приложения , 218 : 213–224, doi : 10.1016/0024-3795(93)00173-W , MR 1324059. См. в частности обсуждение на стр. 218.

Ссылки

Чэнь, Вай-Кай (1976), Прикладная теория графов , North Holland Publishing Company, ISBN 0-7204-2371-6.
Хедетниеми, СТ, Якобс, ДП, Ласкар, Р. (1989), Неравенства, включающие ранг графа. Журнал комбинаторной математики и комбинаторных вычислений , т. 6, стр. 173–176.
Бевис, Джин Х., Блаунт, Кевин К., Дэвис, Джордж Дж., Домке, Гейла С., Миллер, Валери А. (1997), Ранг графа после добавления вершин. Линейная алгебра и ее приложения , т. 265, стр. 55–69.

[1] Weisstein, Eric W. "Graph Rank". Из MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GraphRank.html

[2] Гроссман, Джерролд В.; Кулкарни, Девадатта М.; Шохетман, Ирвин Э. (1995), «О минорах матрицы инцидентности и ее нормальной форме Смита», Линейная алгебра и ее приложения , 218 : 213–224, doi : 10.1016/0024-3795(93)00173-W , MR 1324059. См. в частности обсуждение на стр. 218.