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

редактировать

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

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

Аналогично, нулевое значение графа является нулевым значением его матрицы смежности, равным n - r.

В теории матроидов графов ранг неориентированного графа определяется как число n - c, где c - количество компоненты связности графа. Эквивалентно ранг графа - это ранг ориентированной матрицы инцидентности, связанной с графом.

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

Содержание

1 Примеры
2 См. Также
3 Примечания
4 Ссылки

Примеры

A пример графа и матрицы:

неориентированный граф.

(соответствует четырем ребрам, 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

$(0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0). {\ displaystyle {\ begin {pmatrix} 0 1 1 1 \\ 1 0 0 0 \\ 1 0 0 1 \\ 1 0 1 0 \\\ end {pmatrix}}.}$ ${\ displaystyle {\ begin {pmatrix} 0 1 1 1 \\ 1 0 0 0 \\ 1 0 0 1 \\ 1 0 1 0 \\\ end {pmatrix}}.}$

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

См. Также

Примечания

^Вайсштейн, Эрик У. «График ранга». Материал из MathWorld - веб-ресурса Wolfram. http://mathworld.wolfram.com/GraphRank.html
^Гроссман, Джеррольд У.; Kulkarni, Devadatta M.; Schochetman, Irwin E. (1995), "О минорах матрицы инцидентности и ее нормальной форме Смита", Линейная алгебра и ее приложения, 218 : 213–224, doi : 10.1016/0024-3795(93)00173-W, MR 1324059. См., В частности, обсуждение на стр. 218.

Ссылки

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