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

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

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

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

Содержание

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

Примеры

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

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

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

1234
10111
21000
31001
41010
=

(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, поскольку его векторы-столбцы линейно независимы.

См. Также

Примечания

  1. ^Вайсштейн, Эрик У. «График ранга». Материал из MathWorld - веб-ресурса Wolfram. http://mathworld.wolfram.com/GraphRank.html
  2. ^Гроссман, Джеррольд У.; 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.
Последняя правка сделана 2021-06-03 08:19:05
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте