3. Допустимі сагайдаки

Сагайдак матриці показників є простим сагайдаком. Приклад сагайдака Q з матрицею суміжності [Q]= показує, що не кожний простий сагайдак є сагайдаком матриці показників.

Означення 3.1. Сагайдак Q називається допустимим, якщо icнує зведена матриця показників , така що Q() =Q.

Теорема 3.2. Нехай Q^* – сильно зв’язний простий сагайдак з петлею в кожній вершині. Тоді Q^* – допустимий.

Доведення. Задамо елементи _ij матриці  наступним чином: _ii=0, _ij дорівнює довжині мінімального шляху із вершини “i” в вершину “j” для i j. (Мінімальний шлях існує тому, що Q^* сильно зв’язний сагайдак, але він може бути не єдиним. Можливо існування декількох мінімальних шляхів.)

Покажемо, що =(_ij) – це зведена матриця показників. Довжина мінімального шляху із i в k менше або дорівнює, ніж довжина мінімального шляху із i в к, який проходить через j, тому _ij + _jk  _iк. _ij1 для i j, тому _ij+_ji1 для ij. Отже,  – зведена матриця показників.

Покажемо, що Q()=Q^*. _ij + _ji 2 для i j, тому існує петля в кожній вершині сагайдака Q(). Якщо _ij=1_, то q_ij= {_ik+_kj}-_ij≥ 1, бо _ij≥ 1. Оскільки q_ij{0, 1}, то q_ij =1. Якщо _ij>1, то на мінімальному шляху із i в j існує вершина k, яка відміна від вершин i та j. Тоді

q_ij= {_ik+_kj}-_ij≤_ik+_kj-_ij =0.

Отже, Q()=Q^*. Теорема доведена.

Твердження 3.3. Якщо Q^*– сагайдак з n вершинами, який має рівно n-1 петлю, то він не є допустимим.

Доведення. Припустимо протилежне: сагайдак Q^* – допустимий. Тоді існує матриця показників =(_ij), для якої Q()=Q^*. Нехай в матриці [Q^*] =(q_ij): q_pp=0. Тоді існує індекс i, для якого _ip+_pi =1 (Якщо припустити, що _ip+_pi≥2 для i{1, …, n}, то q_pp=1, одержали протиріччя). Оскільки _ip+_pi =1, то q_ii=0. Одержали протиріччя, оскільки за умовою тільки одна вершина сагайдака Q^* не має петлі. Теорема доведена.

Приклад 3.4. Сагайдак з матрицею суміжності [Q]= не є допустимим. Отже, не кожен сильно зв’язний сагайдак допустимий.

Теорема 3.5. Для довільної пари натуральних чисел p, n таких, що p≤n, pn-1 існує допустимий сагайдак Q з n вершинами, який має рівно p петель.

Доведення. Побудуємо матрицю показників =(_ij)M_n() наступним чином:

_ij=

Легко бачити, що  – матриця показників. _1i + _i1=1 для i=1, …, n-p, тому q_ii=0 для i=1, …, n-p. _ij=1 для ij та i, j>n-p, тому q_ii=1 для i>n-p.

Отже, Q() має рівно p петель.

Приклад. Для n=5, p=2 = Q()= .

Означення. 3.6. Сагайдак називається повним, якщо для довільних двох різних вершин v та w сагайдак має стрілку (v, w).

Теорема 3.7. Повний сагайдак, який має більше ніж дві вершини, є допустимим тоді і тільки тоді, коли він має петлі у всіх вершинах.

Доведення. Повний сагайдак є сильно зв’язним. Тому за теоремою 3.2 повний сагайдак, який має петлю в кожній вершині, є допустимим.

Доведемо, що повний сагайдак, у якого петлі не у всіх вершинах, не є допустимим. Припустимо протилежне, що повний сагайдак Q з n вершинами, який має петлі не у всіх вершинах, є допустимим. Тоді існує зведена матриця показників =(_ij)M_n(), для якої Q()=Q. Сагайдак Q має вершину без петлі. Нехай q₁₁=0. Тоді існує k для якого _1k+ _k1=1. Нехай _1k=1 та _k1= 0 (випадок _1k=0 та _k1= 1 розглядається аналогічно). Оскільки n≥3, то можна знайти j, відмінне від 1 та k. Тоді

1) _1k+_kj ≥_1j 1+_kj ≥_1j _kj ≥_1j-1.

2) _k1+ _1j ≥ _kj _1j ≥ _kj.

З нерівностей 1) та 2) випливає, що _1j ≥ _kj≥ _1j-1. Тому або _kj= _1j-1 або _kj=_1j.

Якщо _kj= _1j-1 то нерівність 1) перетворюється в рівність _1k+_kj =_1j і тоді q_1j=0. Якщо _kj= _1j, то _k1+ _1j = _kj. Тому q_kj=0. Оскільки сагайдак повний, то отримується протиріччя. Теорема доведена.

Приклад 3.8. Сагайдак з матрицею суміжності [Q]= не є допустимим.

Теорема 3.9. Якщо Q – допустимий сагайдак з n вершинами, то для довільного m>n існує допустимий сагайдак Q^* з m вершинами такий, що сагайдак Q є підсагайдаком сагайдака Q^*.

Доведення. Q – допустимий сагайдак, тому існує зведена матриця показників =(_ij)M_n(), для якої Q()=Q. Нехай p – натуральне число, більше за всі елементи матриці . Побудуємо матрицю ^*=(t_ij)M_m():

1) t_ii=0 для i=n+1,…, m,

2) t_ij=_ij для 1≤ i, j≤n,

3) t_ij=p в інших випадках.

Покажемо, що ^* – матриця показників.

Якщо 1≤ i, j≤n, то t_ij+ t_ji= _ij+ _ji≥1. Якщо i або j більше n, то t_ij= t_ji=p. Тому t_ij+ t_ji=2p≥1. Отже, t_ij+ t_ji≥1 для i, j=1, …, m.

Якщо i > n, то t_ik+ t_ij=p і нерівність t_ik+ t_kj≥t_ij виконується. Випадок j > n розглядається аналогічно.

Якщо 1≤ i, j, k≤n, то t_ik=_ik, t_kj=_kj, t_ij=_ij і нерівність t_ik+ t_kj≥t_ij виконується. В інших випадках хоча б одне з чисел t_ik або t_kj дорівнює p. Тому t_ik+ t_kj≥p≥ t_ij. Нерівність t_ik+ t_kj≥t_ij виконується для всіх i, j, k.

Отже, t_ii=0, t_ij+ t_ji≥1 для i, j=1,…, m, i≠j та t_ik+ t_kj≥ t_ij для 1≤ i, j, k≤m. Тому ^*– зведена матриця показників.

Нехай 1≤i, j≤n. Якщо k≤n, то рівність t_ik+ t_kj= t_ij рівносильна рівності

_ik+ _kj=_ij.

Якщо k>n, то t_ik+ t_kj=2p>_ij = t_ij .. Тому q_ij =0 тоді і тільки тоді, коли =0. Отже, сагайдак Q є підсагайдаком сагайдака Q^*. Теорема доведена.