Ранг (теория графов) - Rank (graph theory)

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

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

Аналогично ничтожность графа является нулем его матрицы смежности, которая равна п − р.

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

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

Примеры

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

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

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

=

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

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

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

• Ранг цепи
• Ранг цикла
• Nullity (теория графов)

Примечания

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

Рекомендации

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