Об орграфах, имеющих минимальные вершинные 1-расширения с малым количеством дуг



жүктеу 65.49 Kb.
Дата07.02.2019
өлшемі65.49 Kb.

ОБ ОРГРАФАХ, ИМЕЮЩИХ МИНИМАЛЬНЫЕ ВЕРШИННЫЕ 1-РАСШИРЕНИЯ С МАЛЫМ КОЛИЧЕСТВОМ ДОПОЛНИТЕЛЬНЫХ ДУГ

Абросимов М.Б., Моденова О.В.

Саратовский государственный университет им. Н.Г.Чернышевского



Саратов, Россия
В работе используются основные понятия теории графов в соответствии с работой [1].

Ориентированным графом (далее просто орграфом) называется пара , где V – конечное непустое множество, называемое множеством вершин, а α – отношение на множестве вершин V, называемое отношением смежности. Граф с симметричным и антирефлексивным отношением смежности называется неориентированным графом (далее просто неографом).

Симметризацией орграфа называется неограф , то есть симметризация орграфа получается заменой дуг ребрами и удалением петель.

Граф G* = (V*, α*) называется минимальным вершинным k-расширением (МВ-kР) n-вершинного графа G = (V, α), если выполняются следующие условия:

1) граф G* является вершинным k-расширением графа G, то есть граф G допускает вложение в каждый подграф графа G*, получающийся удалением любых его k вершин;

2) граф G* содержит n + k вершин, то есть |V*| = |V| + k;

3) α* имеет минимальную мощность при выполнении условий 1) и 2).

Понятие минимального вершинного k-расширения введено на основе понятия оптимальной k-отказоустойчивой реализации, которое было предложено Хейзом в работе [2]. Оказалось, что задача является вычислительно сложной [3]. В работе [4] исследовалась задача описания неографов с числом дополнительных ребер до 3. В данной работе рассматривается аналогичная задача для орграфов.

В работе [5] приводится лемма, устанавливающая связь между минимальными вершинными k-расширениями неориентированного графа и его ориентации.

Лемма 1. Пусть G* есть минимальное вершинное k-расширение орграфа G. Тогда симметризация G* является вершинным k-расширением симметризации G.

Следствие. Число дополнительных дуг минимального вершинного k-расширения орграфа G не менее числа дополнительных ребер минимального вершинного k-расширения симметризации орграфа G.

В работе [4] были получены следующие результаты (теоремы 1-4).



Теорема 1. Минимальное вершинное k-расширение, причем единственное с точностью до изоморфизма, вполне несвязного n-вершинного графа On есть вполне несвязный (n + k)-вершинный граф On+k. Никакие другие графы не могут иметь минимальные вершинные k-расширения с нулевым числом дополнительных ребер.

Теорема 2. Графы со степенным множеством {1, 0} и только они имеют минимальное вершинное 1-расширение, которое отличается на одно дополнительное ребро, причем это расширение единственно с точностью до изоморфизма.

Теорема 3. Среди связных графов только цепи имеют минимальное вершинное 1-расширение, которое отличается на два дополнительных ребра, причем это расширение единственно с точностью до изоморфизма.

Теорема 4. Среди несвязных графов без изолированных вершин только графы вида  при n > 1 имеют минимальное вершинное 1-расширение, которое отличается на два дополнительных ребра, причем это расширение имеет вид , и оно единственно с точностью до изоморфизма.

С учетом следствия из леммы и теорем 1-4 орграфы, которые имеют минимальные вершинные 1-расширения с числом дополнительных дуг не более 2, следует искать среди ориентаций указанных в теоремах графов. Очевидно, что теорема 1 справедлива и для орграфов, т.е. минимальное вершинное k-расширение, причем единственное с точностью до изоморфизма, вполне несвязного n-вершинного орграфа есть вполне несвязный (k)-вершинный орграф. Никакие другие орграфы не могут иметь МВ-kР с нулевым числом дополнительных дуг. Для остальных случаев удалось получить следующие результаты.



Теорема 5. Среди орграфов без петель орграфы, полученные объединением n 2-вершинных цепей (n > 0) с m изолированными вершинами (m > 0), и только они имеют минимальные вершинные 1-расширения с одной дополнительной дугой, причем это расширение единственно с точностью до изоморфизма. (Рис. 1)

Рис. 1. Орграфы, полученные объединением n 2-вершинных цепей и m изолированных вершин, и их МВ-1Р


Теорема 6. Среди орграфов с петлями орграфы, полученные объединением n вершин с петлями (n > 0) и m изолированными вершинами (m ≥ 0), и только они имеют минимальное вершинное 1-расширение с одной дополнительной дугой, причем это расширение единственно с точностью до изоморфизма (Рис. 2).

Рис. 2. Орграфы, полученные объединением n вершин с петлями с m изолированными вершинами, и их МВ-1Р


Следствие. Орграфы, полученные объединением n вершин с петлями (n > 0) с m изолированными вершинами (m ≥ 0), имеют минимальные вершинные k-расширения с k дополнительными дугами, причем эти расширения единственны с точностью до изоморфизма.
Теорема 7. Среди связных орграфов только гамильтоновы цепи имеют минимальное вершинное 1-расширение, которое отличается на две дополнительные дуги, причем это расширение единственно с точностью до изоморфизма для цепей с количеством вершин больше двух. Для 2-вершинных цепей существует два неизоморфных МВ-1Р: циклическая и транзитивная тройки (Рис.4).

Рис. 3. Гамильтонова цепь и ее МВ-1Р – гамильтонов цикл



Рис. 4. Цепь и два ее неизоморфных МВ-1Р


Теорема 8. Среди несвязных орграфов без изолированных вершин и без петель при > 2 только орграфы вида , где циклы Cn+1 являются контурами, а цепь Pn – гамильтоновой цепью, имеют минимальное вершинное 1-расширение, отличающееся на две дополнительные дуги, причем это расширение имеет вид , где Cn+1гамильтоновы циклы, и оно единственно с точностью до изоморфизма. При n = 2 существует два орграфа (объединение 2-вершинной цепи и транзитивных троек, объединение цепи и циклических троек), МВ-1Р которых отличаются на две дополнительные дуги (Рис. 5).

Рис. 5. Орграфы вида , где цепь и циклы являются гамильтоновыми, и их МВ-1Р


Теорема 9. Среди несвязных орграфов с изолированными вершинами и без петель МВ-1Р с двумя дополнительными дугами имеют только орграфы вида:

1) объединение гамильтоновых n-вершинных цепей (n > 1) с любым количеством изолированных вершин. При n > 2 МВ-1Р единственно с точностью до изоморфизма, при n = 2 существует два неизоморфных МВ-1Р;

2) объединение 3-вершинной негамильтоновой цепи и m изолированных вершин, где > 2 (МВ-1Р – объединение двух изоморфных цепей и m – 2 изолированных вершин, единственно с точностью до изоморфизма) (Рис. 6);

3) объединение орграфов вида  при > 2, где циклы Cn+1 являются контурами, а цепь Pn – гамильтоновой цепью, с изолированными вершинами (МВ-1Р единственно с точностью до изоморфизма);

4) объединение 2-вершинной цепи с транзитивными или циклическими тройками и любым количеством изолированных вершин (расширение будет единственным с точностью до изоморфизма).

Рис. 6. Объединение 3-вершинной цепи и 2 изолированных вершин и МВ-1Р


Следствие. Объединение n-вершинных негамильтоновых цепей с n – 1 изолированными вершинами имеет вершинные 1-расширения c n – 1 дополнительными дугами.

Теорема 10. Среди несвязных орграфов с изолированными вершинами и с петлями только орграфы следующего вида имеют минимальные вершинные 1-расширения с двумя дополнительными дугами, причем единственные с точностью до изоморфизма:

1) объединение n 2-вершинных цепей с петлями в источниках (n > 0) с m изолированными вершинами (m > 0) (Рис. 7);

2) объединение n 2-вершинных цепей с петлями в стоках (n > 0) с m изолированными вершинами (m > 0) (Рис. 8);

3) объединение n 2-вершинных цепей с петлями на концах (n > 0) с m вершинами c петлями (> 0) и p изолированными вершинами (p ≥ 0) (Рис. 9).



Рис. 7. Случай 1 из теоремы 10



Рис. 8. Случай 2 из теоремы 10



Рис. 9. Случай 3 из теоремы 10


СПИСОК ЛИТЕРАТУРЫ

  1. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997.

  2. Hayes J.P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. Vol.C.25. №9. P. 875--884.

  3. Абросимов М.Б. О сложности некоторых задач, связанных с расширениями графов // Матем. Заметки. 2010. № 88:5, С. 643–650.

  4. Абросимов М.Б. Характеризация графов с заданным числом дополнительных ребер минимального вершинного 1-расширения // Прикладная дискретная математика. – 2012. № 1. – С. 111-120.

  5. Абросимов М.Б. Минимальные вершинные расширения направленных звезд // Дискрет. матем. – 2001. №23:2. – С. 93-102.


Достарыңызбен бөлісу:


©kzref.org 2017
әкімшілігінің қараңыз

    Басты бет