Минимальный ранг графа - 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 п 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 я = 1, ldots, к}$ .^[8]