Минимальный ранг графа - Minimum rank of a graph - Wikipedia

В математике минимальный ранг это график параметр ${\displaystyle \operatorname {mr} (G)}$ для график грамм. Это было мотивировано Граф инвариант Колена де Вердьера.

Определение

В матрица смежности из неориентированный граф это симметричная матрица чьи строки и столбцы соответствуют вершинам графа. Все его элементы равны 0 или 1, а элемент в строке я и столбец j отлична от нуля, когда вершина я смежна с вершиной j в графике. В более общем плане обобщенная матрица смежности - любая симметричная матрица действительных чисел с одинаковым набором ненулевых значений по диагонали (диагональные элементы могут быть любыми действительными числами). Минимальный ранг ${\displaystyle G}$ определяется как наименьший классифицировать любой обобщенной матрицы смежности графа; это обозначается ${\displaystyle \operatorname {mr} (G)}$.

Характеристики

Вот некоторые элементарные свойства.

• Минимальный ранг графа всегда не больше, чем п - 1, где п - количество вершин в графе.^[1]
• Для каждого индуцированный подграф ЧАС данного графа грамм, минимальный ранг ЧАС не более, чем минимальный ранг грамм.^[2]
• Если график отключен, то его минимальный ранг равен сумме минимальных рангов его связанные компоненты.^[3]
• Минимальный ранг - это инвариант графа: изоморфный графы обязательно имеют одинаковый минимальный ранг.

Характеристика известных семейств графов

Несколько семейств графов можно охарактеризовать с помощью их минимальных рангов.

• За ${\displaystyle n\geq 2}$, то полный график K_п на п вершина имеет минимальный ранг один. Единственные графы, которые связаны и имеют минимальный ранг один, - это полные графы.^[4]
• А граф путей п_п на п вершины имеют минимальный ранг п - 1. Единственный п-вершинные графы с минимальным рангом п - 1 - графы путей.^[5]
• А график цикла C_п на п вершины имеют минимальный ранг п − 2.^[6]
• Позволять ${\displaystyle G}$ быть 2-связный график. потом ${\displaystyle \operatorname {mr} (G)=|G|-2}$ если и только если ${\displaystyle G}$ является линейным 2-деревом.^[7]
• График ${\displaystyle G}$ имеет ${\displaystyle \operatorname {mr} (G)\leq 2}$ тогда и только тогда, когда дополнение ${\displaystyle G}$ имеет форму ${\displaystyle (K_{s_{1}}\cup K_{s_{2}}\cup K_{p_{1},q_{1}}\cup \cdots \cup K_{p_{k},q_{k}})\vee K_{r}}$ для соответствующих неотрицательных целых чисел ${\displaystyle k,s_{1},s_{2},p_{1},q_{1},\ldots ,p_{k},q_{k},r}$ с ${\displaystyle p_{i}+q_{i}>0}$ для всех ${\displaystyle i=1,\ldots ,k}$.^[8]

Примечания

1. Фаллат – Хогбен, наблюдение 1.2.
2. Фаллат – Хогбен, Наблюдение 1.6.
3. Фаллат – Хогбен, Наблюдение 1.6.
4. Фаллат – Хогбен, наблюдение 1.2.
5. Фаллат – Хогбен, следствие 1.5.
6. Фаллат – Хогбен, Наблюдение 1.6.
7. Фаллат – Хогбен, теорема 2.10.
8. Фаллат – Хогбен, теорема 2.9.

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

• Фаллат, Шон; Хогбен, Лесли, «Минимальный ранг симметричных матриц, описываемых графом: обзор», Линейная алгебра и ее приложения 426 (2007) (PDF), стр. 558–582.