Перейти к навигации Перейти к поиску
| Актуальные темы на |
| Связь с графиком |
|---|
В теории графов , раздел математики, то ранг из неориентированного графа имеет два несвязанных определение. Пусть n равно количеству вершин графа.
- В матричной теории графов ранг r неориентированного графа определяется как ранг его матрицы смежности .
- Аналогично, нулевое значение графа равно нулю его матрицы смежности, равной n - r .
- В матроидной теории графов ранг неориентированного графа определяется как число n - c , где c - количество компонент связности графа. [1] Эквивалентно, ранг графа - это ранг ориентированной матрицы инцидентности, связанной с графом. [2]
- Аналогично, нулевое значение графа равно нулю его ориентированной матрицы инцидентности, заданной формулой m - n + c , где n и c такие же, как указано выше, а m - количество ребер в графе. Нулевое значение равно первому числу Бетти на графике. Сумма ранга и аннулирования - это количество ребер.
Примеры [ править ]
Пример графика и матрицы:
(соответствует четырем ребрам, e1 – e4):
| знак равно |
В этом примере ранг матрицы по теории матриц равен 4, поскольку ее векторы-столбцы линейно независимы.
См. Также [ править ]
Заметки [ править ]
- ^ Weisstein, Эрик В. "Graph Rank". Материал из MathWorld - веб-ресурса Wolfram. http://mathworld.wolfram.com/GraphRank.html
- ^ Гроссман, Джерролд У .; Kulkarni, Devadatta M .; Schochetman, Ирвин Е. (1995), "О миноров матрицы заболеваемости и ее нормальной форме Смита", Линейная алгебра и ее применения , 218 : 213-224, DOI : 10.1016 / 0024-3795 (93) 00173-З , Руководство по ремонту 1324059. См., В частности, обсуждение на стр. 218.
Ссылки [ править ]
- Чен, Вай-Кай (1976), прикладная теория графов , издательство North Holland Publishing Company, ISBN 0-7204-2371-6.
- Хедетниеми, С.Т., Якобс, Д.П., Ласкар, Р. (1989), Неравенства, связанные с рангом графа. Журнал комбинаторной математики и комбинаторных вычислений , вып. 6. С. 173–176.
- Бевис, Джин Х., Блаунт, Кевин К., Дэвис, Джордж Дж., Домке, Гайла С., Миллер, Валери А. (1997), Ранг графа после добавления вершин . Линейная алгебра и ее приложения , т. 265. С. 55–69.