Недействительность (теория графов)

Нуль может означать любое графа . в математическом предмете теории графов из двух несвязанных чисел Если граф имеет n вершин и m ребер, то:

• В матричной теории графов нуль графа равна нулю матрицы смежности A графа. Нулевое значение A определяется выражением n − r , где r — ранг матрицы смежности. Эта нуль равна кратности собственного значения 0 в спектре матрицы смежности. См. Цветкович и Гутман (1972), Ченг и Лю (2007), а также Гутман и Боровичанин (2011).
• В теории матроидов нуль графа — это нуль ориентированной матрицы инцидентности M, связанной с графом. Нулевое значение M определяется выражением m − n + c , где c — количество компонентов графа, а n — c — ранг ориентированной матрицы инцидентности. Это имя используется редко; это число более известно как ранг цикла , цикломатическое число или ранг цепи графа. Он равен рангу графического матроида графа. Это также равно нулю матрицы Лапласа графа, определяемой как L = D − A , где D — диагональная матрица степеней вершин; лапласова нуль равна рангу цикла, поскольку L = M M ^Т ( M раз собственное транспонирование).

См. также

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

Ссылки

• Бо Ченг и Болиан Лю (2007), О ничтожности графов. Электронный журнал линейной алгебры , вып. 16, статья 5, стр. 60–67.
• Драгош М. Цветкович и Иван М. Гутман (1972), Алгебраическая кратность числа ноль в спектре двудольного графа. Математический журнал (Белград) , вып. 9, с. 141–150.
• Иван Гутман и Бояна Боровичанин (2011), Недействительность графов: обновленный обзор. Зборник Радова (Белград) , т. 14, нет. 22 (Избранные темы по применению спектров графов), стр. 137–154.