close

Вход

Забыли?

вход по аккаунту

?

О классификации графов основанной на минимальном ранге матрицы ассоциированной с графом.

код для вставкиСкачать
УДК
Вестник СПбГУ. Сер .
519.17
10, 2004 ,
вып.
3
В. Ю. Добрынин
О КЛАССИФИКАЦИИ ГРАФОВ, ОСНОВАННОЙ НА МИНИМАЛЬНОМ
РАНГЕ МАТРИЦЫ, АССОЦИИРОВАННОЙ С ГРАФОМ
1.
Введение. Есть несколько хорошо известных функций графа, которые можно
представить в терминах минимума ранга f\екоторой матрицы, ассоциированной с гра­
фом. Упомянем две такие функции.
Первая функция есть минимальная размерность ортанормального помечивания
графа.
Ортанормальным помечиванием размерности
множество вершин, а Е~
{1, ... ,n}-
(
и:
такое, что иi · Uj
всех
i
Е
V.
=
~
)
d
графа
ного помечивания графа
d( G)
Е), где
V
-множество ребер, есть отображение
v -t ]Rd
О для всех пар не смежных вершин
Обозначим через
G = (V,
i,j
Е
V и llиill2 = 1 для
минимально возможную размерность ортанормаль­
(Lasl6 Lovasz) рассмотрел эту функцию в
B(G) [1] . Функция B(G) вычислима за
полиномиальное время и ограничена снизу и сверху соответственно а( G) - мощностью
наибольшего независимого множества вершин и х( G) - наименьшим числом клик, по­
крывающих все вершины графа G.
Пусть ei Е JRd -орт, в котором все компоненты кроме i-й равны нулю, а i-я компо­
нента равна 1. ПустьМ-некоторое независимое множество вершин графа G. Тогда
{ иi : i Е М} есть система попарно ортогональных векторов. Б связи с этим
G.
Ласло Ловас
связи с изучением им же введенной функции
L(e1·иi) 2 ~ je 1 12 = 1.
iEM
Следовательно,
IMI
.
1
~ mш max
,
и iEV(G) (е 1 · щ) 2
(1)
где минимум берется по всем ортанормальным помечиваниям графа
неравенства
Из
( 1)
(1)
и есть предложенная Ласло Ловасом функция
G.
Правая часть
O(G).
непосредственно следует, что
a(G)
~
O(G).
Кроме того, Ловас доказал, что
B(G) ~ d(G) ~ x(G).
Очевидно, что
социированной с
d( G) можно
G. Пусть
представить в терминах минимума ранга матрИцы, ас­
Ato(G) = {Х: Х Е !Rnxn,X = хт,Х t О,
©В. Ю. Добрынин,
30
2004
I - A(G):::;
где !Rn x n -
A(G) -
Х:::;
множество всех вещественных
матрица смежности графа
G;
+ A(G)},
I
х
n
n
матриц;
единичная матрица;
I -
Х ~ О означает положительную полуопреде­
ленность матрицы Х. Таким образом, если Х Е
Ato (G),
то
Х =УтУ,
здесь У - вещес-.rвенная матрица размерности
ортанормальное помечивание графа
G.
rk(X)
х
все столбцы которой задают
n,
Следовательно,
d(G) :::;
min
rk(X).
XEAto(G)
Вместе с тем пусть У есть
помечивание графа
G
d( G)
х
n-
матрица, задающая некоторое ортанормальное
минимальной размерности. Тогда
уту Е Ato(G)
и
~
d(G)
min
rk(X).
XEAto(G)
Итак,
d(G) =
min
XEAto(G)
rk(X).
Вторая упоминаемая функция графа, представимая с помощью ранга некоторой
матрицы, ассоциированной с графом, есть хорошо известная функция
связана с топологическими свойствами графа.
только тогда, когда
В работе
[3)
Например, граф
G
J.L(G) [2) , которая
планареи тогда и
J.L(G) :::; 3.
изучалась функция
J.L(G)
и, в частности, было показано, что для каж­
дого отличного от К r графа
G
где для заданного графа Н
= n- v(G)- 1,
= (V, F), IVI = n, v(H) есть
J.L(G)
ричной
1)
n
Aij
х
n
= 1, если ij
Е F, и Aij
если ij Е
< 1,
F;
2) А~ О;
3) если Х есть симметричная n х n матрица, такая что
и АХ
=
минимальный ранг симмет­
матрицы А, удовлетворяющей следующим условиям:
О, то Х
=
Xij =О для
Рассмотрим теперь такой класс ассоциированных с графом
A(G)
= {Х: Х Е !R.пхп,
Обозначим через
ij Е FU{ ii; i Е V}
О.
r(G)
G
Х = хт, I- A(G):::; Х:::; I
матриц:
+ A(G)}.
функцию графа, равную минимуму ранга матрицы из класса
A(G):
r(G)
= XEA(G)
min rk(X).
В настоящей работе изучается возможность использования функции
• рых
r(G)
и некото­
близких ей функций для классификации графов.
31
2.
Основные свойства функции
r(G).
Свойства функции
r(G)
будем рассмат­
ривать в сопоставлении со свойствами нескольких родственных функций.
В качестве базового класса рассмотрим
= {Х: Х Е ~nxn,
A(G)
= хт,
Х
I - A(G) ~ Х ~ I
+ A(G)}.
Три следующих класса являются подклассами базового класса:
•
класс неотрицательных матриц
A~o(G) = {Х: Х Е A(G), Х
•
2:: 0},
класс положительно полуопределенных матриц
Ato(G) = {Х: Х Е A(G), Х ~ 0},
•
класс
С (G) = { Х : Х Е А( G), Х = В т В, В
2:: О}.
Таким образом,
C(G)
с A~o(G)
n Ato(G).
Напомним, что
r(G) =
d(G)
Обозначим через
r + (G)
min rk(X),
XEA(G)
= XEAto(G)
min rk(X).
функцию графа, равную минимуму ранга матрицы из класса
A~o(G):
r +(G) =
min
XEA~o(G)
rk(X).
Заметим, что нет необходимости предлагать новое имя для функции, равной мини­
мальному рангу матрицы из класса
Теорема
1.
Дл.я каждого графа
благодаря следующей теореме
C(G),
G
x(G) =
Вернемся к рассмотрению функций
[4] .
min rk(X).
XEC(G)
r(G), r +(G) и d(G). Из определений и теоремы 1
непосредственно вытекает, что
a(G) ~ r(G) ~ d(G), r +(G) ~ x(G).
Далее рассмотрим соотношения между
2.1.
Функции
r(G)
и
d(G).
(2)
r(G) и остальными функциями из (2).
Начнем с рассмотрения именно этой пары функций,
так как имеется ряд свидетельств в пользу того, что между
ная связь. Более того, открытым остается вопрос
-
r(G) и d(G) есть определен­
являются ли эти функции графа
. различными?
Лемма
32
2 [5).
Дл.я каждого графа G равеNсmво a(G) = r(G) вле-ч.ет a(G) = d(G).
Д о к а з а т е л ь с т в о. Пусть
a(G)
= r(G) = k,
Х Е
A(G)
и
rk(X)
= k.
Б ез
потери общности положим
Х -_ (Ik
i)·
ут
С.1едовательно, Z = уту и
Таким образом, столбцы матрицы
(Ik
н ости
d(G)
k
графа
Функция
G.
d( G)
Следовательно,
У) дают ортанормальное помечиванне размер­
= k.
интересна тем, что ее можно использовать для построения верхней
о ценки функции х( G). В то же время получить подобную оценку на основе функции
a(G) невозможно [6, 7), и этот вопрос остается открытым для функции r(G).
Следующая лемма, принадлежащая Андрею Котлову (устн. сообщение, 2001), дает
п риведеиную оценку для x(G) в терминах d(G). Следует отметить, что Котлов, Лова:с
и Фишкинд получили ряд интересных результатов относительно связи хроматического
ч исла графа и ранга его матрицы смежности
Лемма
[8-10).
(А. Котлов). Пустъ щ, ... , иn задает ортонор.малъное по.ме-чивание графа
3
d и Ь 1 , .. . , bk естъ ортогоналъный базис нех:оторого линейного прост­
ра нства L С JRd, тшх:ой -что иi · Ьj ~О дл.я i = 1, ... , n и j = 1, ... , k. Тогда
G
размерности
Д о к аз а т е ль с т в о. Без потери общности положим, что в L лежат векторы
, ... , и т и иi ~ L для i > т. Здесь т ~ О. Мы можем раскрасить векторы и 1 , ... , ит не
бо.1ее чем в k цветов следующим образом (здесь под раскраской понимаем такое сопоса вление векторам цветов, при котором ортогональные векторы получают различные
uв ета). Для каждого
i :::; т вектор иi получает цвет l, где l есть наименьшее целое, таn- т векторы иm+l, ... , иn могут быть раскрашены
не более чем в 2d-k цветов. Действительно, пусть bk+I, ... , bd - ортогональный базис в
~ое что иi
· bt
> О.
Далее, остальные
об щем положении ортогонального дополнения к пространству
с
: Ui
1-t (sign(щ
L.
Тогда функция
· bk+I), ... , sign(иi · bd))
о пределяет допустимую раскраску векторов иm+l, ... , иn в G не более чем в 2d-k цветов.
Следствие
4·
С исполъзование.м обоз!!!!:.--чений, введенных выше,
x(G):::; min{k, т}+ min{n- т, 2d-k}.
Предыдущий результат можно использовать для характеризации графов, дополни­
тельных к двудольным, в терминах функции
граф, то
d(G) = 2.
x(G)
Обратно, пусть
вует вектор и
k = 1,
= x(G) = 2.
: и· иi
>
d( G). Если G - непустой двудольный
d(G) :::; x(G) и d(G) > 1 для непустого графа, то
Так как
d( G) = 2.
Не умаляя общности, можно считать, что сущест­
О для всех иi,
т= О и, по следствию
i = 1, ... , n, и и {f иi для всех иi, i = 1, .. . , n. Тогда
4,
x(G) :::; min{1, О}+ min{n, 21 } = 2.
Следовательно,
G-
двудольный граф.
33
Теперь сопоставим функции
Теорема
Для
5 [5).
и т(G) при малых значениях.
d(G)
i:::; 3
т(G) =
i тогда и тоЛЪ'К,О тогда, 1\,Огда d(G) ~ i .
Д о к аз а т е л ь с т в о.
Очевидно, что т(G) =
1 <=? a(G) = 1 <=? d(G)
1 <=?
r + (G) = 1.
Пусть
d(G) = 2.
Тогда, по следствию
a(G) =
т(G) =
4, :X(G) = 2 и,
d(G)
=т +(G) =
таким образо~,
x(G) = 2.
Пусть т(G)
= 2. Тогда a(G) = 2 и, по лемме 2, d(G) = 2.
d(G) = 3. Тогда т(G) = 3 следует из предыдущего утверждения.
Пусть т(G) = 3. Тогда 2 :::; a(G) :::; 3.
В случае a(G) = 3 равенство d(G) = 3 следует из леммы 2.
Пусть a(G) = 2. Пусть Х Е A(G) и rk(X) = 3. Обозначим через G[X) остовной
п одграф графа G, который содержит ребро ij тогда и только тогда, когда Xij f О .
Пусть
Пусть
V (G) = V1
u · · · u Vm,
где
• Vi n 1.-j
•
=
0,
если i
f
j;
= О, если и только если
Xik
Vz, l
{1, ... ,т};
• существует k Е {1, ... , n}
i Е
Xjk
= О для всех k Е {1, . . . , n} при i, j
Е
Е
Vz•,
j Е Vzи и l'
f
такое, что Xik
Иными словами, множество вершин
ный подграф графа
Vi.
Пусть Vi Е Vi, i
G[X),
f
О и Xjk =О или Xik =О и Xjk
f
О при
l" .
Vi
индуцирует максимальный по включению пол­
Vi
такой что все вершины из
в
G[X)
имеют одних и тех же
соседей вне
Е { 1,
. .. , т}
и
где х(~~·::::.~~) есть подматрица матрицы Х, стоящая на пересечении строк с номерами
из
{i 1, .. . ,ik} и столбцов с номерами из {j1, ... ,jl} ·
{ 1, ... , т} существует k Е { 1, . . . , т} такое, что
Тогда для каждой пары i,j Е
или
Xv;,vk =О И Xv;,vk
Очевидно, что
a(G) :::; ·rk(X') = rk(X).
т+(G).
Без потери общности положим, что
f
О.
При этом
d(G[X'))
~
d(G)
и т+(G[Х'))
>
V(G[X')) = {1 , ... , т} и 12 (j. E(G[X']), 23 (j.
E(G[X']), 13 Е E(G[X')). Действительно, если для каждой пары не смежных вершин
. графа G[X') эти вершины смежны всем другим вершинам графа G[X') , то d(G[X')) = 2
• и, следовательно, d(G) = 2. Вместе с тем, если 13 (j. E(G[X']), то a(G) = 3.
34 .
Следовательно,
Пусть lxl < 1. Тогда матрица (~ О1 х~)
положительно определенная, Х' поло-
О
жительна полуопределенная и, таким образом, Х' = рт F, где F - 3 х т-матрица.
Столбцы матрицы
F
представляют ортанормальное помечивание графа
рое может быть распространено на граф
Пусть lxl
= 1.
G.
Следовательно ,
d(G)
= 3.
G[X'],
кото­
Тогда lx'(~:~:~) 1=О. Без потери общности положим, что
2,3,4) 1
Х' ( 2,3,4
=/-
о.
1
Тогда
1 , 2 , 3,4
x'k ....rn)
Ранг матрицы Х'
(1
•···
,rn
равен
3
(~
О
х
У1
1
о
У2
О
У2
1
Уз
Уз
1
х
=
(
1 , 2,3,4)
1
о
У1
...
...
)
и рангу матрицы
о
о
z
1
о
У2
о
1
Уз
У2
Уз
1
...
...
)
которая получена из предыдущей матрицы вычитанием третьей строки и столбца, ум­
ноженных на х, из первой строки и столбца соответственно.
Следовательно, все эле­
менты первой строки последней матрицы должны быть равны О. Таким образом, вер­
шины
1
и
3
принадлежат одному и тому же множеству
Vi.
Из этого противоречия
следует, что 1х 1 =1Следствие
1.
6. Если d(G) = 4,
то
r(G) = 4.
2.2. Функции r(G) и a(G). Теперь можно показать, что функции r(G) и a(G)
2 и х(С5 ) = 3. Так как С5 не
d(C5 ) = 3. Следовательно , по
лемме 2 r(C5) = 3.
Имеются графы, для которых r(G) = a(G) , например совершенные. Как можно
охарактеризовать все графы, для которых это равенство имеет место? Из леммы 2
следует, что это все такие графы, для которых а( G) = d( G). По следствию 4 заклю­
различны. Рассмотрим цикл С5 . Известно, что а(С5 ) =
является двудольным · графом, то, по ранее доказанному,
чаем, что для них выполняется такженеравенство
x(G) :::;
2a:{G)-1_
Отметим , что для произвольнаго графа нельзя оценить сверху величину х( G) в
терминах функции а( G).
35
Естественно возникает вопрос- насколько велика может быть величинах( G)- а( G)
в сл учае, когда
В работе
a(G) = r(G)?
[11]
Е. В. Просалупав приводит после­
.1Овательность связных графов {Гi}, для . которых а(Гi) = d(Гi )
х( Г i) - а(Гi) ~
liJ ·
<
х(Гi), причем
.
Представляет интерес также вопрос о дополнительных условиях на граф
ко торых из равенства
вытекает равенство
a(G) = r(G)
a(G) = x(G).
G,
при
В работе
[12]
пр иводится следующий результат.
Теорема
7. Если в графе G нет двух, -ци-х;лов с4 без хорд с общим ребром, то
a(G) = r(G) вле"lет a(G) = x(G).
Д о к аз а т е ль с т в о . Пусть для графа G выполняются равенства a(G) = r(G)
o( G) = rk(X), Х Е A(G). Не умаляя общности,
равежтво
н
Х = (Ii~) · ~)
н
Z =
уту_
Это означает, что столбцы матрицы
нне и графа G.
(Ia(G), У)
задают ортанормальное помечива­
Покажем, что для любых вершин l Е {1, . ..~, a(G) } , i, j Е V(G) \
.... , a(G) }, если вершины i и j не смежны, ez · иi '=1 О и е 1 • иi '=1 О , то существует
{1, . . . , a(G) }, т ':ll, которая, как и вершина l , смежна с вершинами i
вер шина т Е
11
J.
Действительно, так как
i
и
j
не смежны, то
a(G)
L
иi · Uj =
(е s · щ) (е s
· Uj)
= О.
s=l
Но слагаемое
(ez · иi)(ez · щ)
в последней сумме не равно О. Следовательно, существует
по крайней мере еще одно иенулевое слагаемое
т. е. вершина т Е М, смежная с
Пусть
V
= V1 U · · · U Vq,
i
и
j.
q ~ a(G) есть разбиение множества вершин графа G на
подмножества такое, что
• l Е V[, l = 1, ... , a(G);
• если i Е V(G) \ {1, ... , a(G)}, i Е V[, 1 :::; l:::; a(G), то ez · иi '=1 О;
• если i,j Е V[, 1:::; l:::; q, то вершины i и j смежны.
Очевидно, что такое разбиение всегда можно построить . Например, можно взять
q = n,
и каждое
Vi
будет содержать ровно одну вершину.
Итак, если это разбиение имеется, то каждое
тельно,
Vi
порождает в
G
клику и, следова­
x(G) :::; q.
Не умаляя общности, можно полагать, что никакое из множеств
{V1 , . .. , Va(G)} немо­
Va(G)+l, ... , Vq.
жет быть расширено за счет добавления каких-либо вершин из множеств
Обозначим М=
{1, ... , a(G) }.
a(G) < x(G) .
Тогда множество S = Va(G)+l U ... U Vq не пусто .
S - произвольная вершина из S. Тогда существует l Е М такое, что еz · и х ':1 О
·(ибо их '=1 0). Так как, по ранее сделанному предположению, множество Vt не может
Предположим, что
Пусть х Е
36
быть расширено за счет добавления вершины х, то существует вершина х 1 Е
смежная с х . Тогда должна су ществовать вершина т Е М, т =f=.
l,
Vi,
не
смежная с х и х 1 •
В множестве У'тп также должна существовать вершина Xm, н е смежная с х, так как
это множество, по предположению, н ельзя расширить за счет добавлениях. Но тогда
в М должна иметься вершин а у =f=. т, смежная с х и Xm· При этом вершины
l и у могут
сов п адать .
4 без хорд с общим ребром: (l, х 1 , т, х, l)
l , то имеются циклы (l, х, т, XL, l) и (т, х, l , Xm, т).
Получено противоречие с условием, н~оженным на граф G, - нет двух циклов
.],ЛИНЫ 4 без хорд с общим ребром . Следовательно , q = a (G) = x(G).
Если у =f=.
l , то
в
G
имеются два цикла длины
и (т, х, у , Xm, т) . Если у=
2.3. Функции r(G) и r +(G) . В п. 2.2 отмечалось, что в обще м случае из р авенства
a(G) = r(G) н е следует a(G) = x(G). Одн ако при переходе от r(G) к r+(G) ситуация
~1еняется
[13].
Теорема
8.
Дл.я любого графа
G a(G)
= r +(G)
Д о к аз а т е ль с т в о. Пусть для графа
a(G) = r +(G).
Пусть Х Е A ~o( G) и
вле-чет a(G) = x(G).
G = (V(G) , E(G)) выполняется р авенство
r +(G) = rk(X).
Х-
(Ia(G)
ут
Не умаляя общности,
i)·
Следовател ьно , Z = уту и столбцы матрицы
(Ia(G)
У)
задают неотричат елъ ное ортанормальное помечиванне и+ графа
G разм ерности a(G):
и+ : V(G) -+ ffi.~(G) .
Построим разбиени е множества вершин
V (G) на непересекающиеся подмножеств а
i = 1, ... , а (G) . В ершину j Е V (G) включаем в множество Vi, если i есть наи­
~Iеньшее целое такое, что иt > О. Очевидно, что каждое Vi порождает в G клику, и,
\ ii,
следовательно,
a(G)
= x(G).
К ак следствие получаем, что функции
функция r +(G) не равна и
r(G) и r +(G) различны. В то же время
x(G). В [13] приводится соответствующий прим ер графа Н,
.J,Л Я которого
а(Н)
3.
< r +(Н) < х(Н).
Итоговая сводка классификационных результатов.
Обозначим чер ез
С { Х} множество графов , удовлетворяющих условию Х.
• Класс C{r(G)
= 1}
= С {полный граф}.
•
Класс
•
Класс
G{r(C) = 2}
= С {дополнительный к двудольному графу} .
C{r(C) = 3}
=С{ d(G) =
3},
~ С{а(С)::; 3 ,х (С)::;
4} .
37
•
Класс G{d(G) =
4}
= 4}.
Класс G{r(G) = a(G)}
= G{d(G) = a(G)},
~ G{r(G)
•
~ G{x(G) :::; 2a(G)-t }.
•
= a(G), нет двух циклов без хорд с общим ребром}
= x(G)}.
.
Класс G{r+(G) = a(G)}
= G{a(G) = x(G)}.
Класс G{r(G)
~ G{a(G)
•
Summary
а
Dobrynin V. Ju. On graph classification based on
graph.
а
minimum rank of
а
matrix associated with
Some elements of а graph classification are presented. This classification is based on а minimum rank function calculated on some matrix classes associated with а graph. The main goal of
classification developed is to study graphs for which а( G) < х( G) is held.
Литература
1. Lovasz L. On the Shannon capacity of graphs 11 IEEE Тrans . Inform. Theory. 1979. Vol. 25.
1- 7.
2. De Verdi ere У. С. Sur la multiplicite de la premiere valeur propre non nulle du laplacien 11
Comment. Math. Helv. 1986. Vol. 61. Р. 254-270.
3. Kotlov А ., Lovasz L. , Vempala S. The Colin de Verdiere number and sphere representation
of а graph 11 ComЬinatorica. 1997. Vol . 17. Р. 483-521.
4. Добрьтин В. Ю. Хроматическое число графа и ранг матрицы 11 Вести . С.-Петерб.
ун-та. Сер . 1: Математика, механика, астрономия. 1995. Вып . 3 (N2 15) . С . 120- 122.
5. Dobrynin V. On the rank of а matrix associated with graph 11 Discrete Mathematics. 2004.
Vol . 276 , N 1-3. Р. 169- 175.
6. Зьисов А. А. 11 Мат. сб . 1949. Т. 24, N~ 2. С. 163- 188.
7. Mycielski F. 11 Collog. Math. 1953. Vol. 3, N 2. Р. 161-162.
8. Kotlov А., Lovasz L. The rank and size of graphs 1IJ. Graph Theory. 1996. Vol. 23.
Р. 185-189.
9. Kotlov А. Rank and chromatic number of а graph 11 J. Graph Theory. 1997. Vol . 26. Р. 1- 8.
10. Fishkind D. Е., Kotlov А. Rank, term rank and chromatic number 11 Discrete Mathematics.
2002. Vol. 250, N 1-3.
11. Просолупов Е. В . О разрыве между минимальной размерностью ортанормального по­
Р.
мечивания и размером наименьшего кликового покрытия графа
Сер.
11
Вести. С.-Петерб. ун-та.
1: Математика, механика, астрономия. 2004 (в печати).
12 . Dobrynin V., Pliskin М., Prosolupov Е. On the functions with values in (a(G), x(G)] 11
Electron. J. ComЬinat. 2004. Vol. 11, N 5.
13. Dobrynin V. On the function "sandwiched" between a(G) and x(G) 11 Electron. J . ComЬinat. 1997. Vol. 4, N 19.
•
Статья поступила в редакцию
19
октября
2004
г.
Документ
Категория
Без категории
Просмотров
4
Размер файла
1 163 Кб
Теги
ранга, ассоциированной, матрица, основанная, классификация, графов, минимальное
1/--страниц
Пожаловаться на содержимое документа