Preview

Информатика

Расширенный поиск

Характеризация и распознавание графов пересечений ребер трихроматических гиперграфов ограниченной кратности в классе расщепляемых графов

Полный текст:

Аннотация

Гиперграф, множество вершин которого можно разбить не более чем на к попарно непересекающихся подмножеств, каждое из которых имеет не более одной общей вершины с любым ребром гиперграфа, называется к-хроматическим. Кратность пары вершин гиперграфа - это число его ребер, содержащих обе вершины пары, тогда кратность гиперграфа - это максимальная кратность пар его вершин. Пусть Lm(k) обозначает класс графов пересечений ребер к-хроматических гиперграфов кратности не выше m. Задача распознавания графов из L1(k) полиномиально разрешима при к = 2 и является NP-полной при к = 3. Вопрос о сложности распознавания графов из Lm(k) при фиксированных к ≥ 2 и m ≥ 2 в настоящее время остается открытым.

Граф называется расщепляемым, если множество его вершин можно разбить на два непересекающихся подмножества, одно из которых является кликой, а другое - независимым множеством вершин. Для любого к ≥ 2 графы из L1(k) характеризуются конечным списком запрещенных порожденных подграфов в классе расщепляемых графов.

Ранее было доказано [1], что для графов из L2(3) существует конечная характеризация в терминах запрещенных порожденных подграфов в классе расщепляемых графов. В настоящей работе этот результат обобщен на класс Lm(3), где фиксированное m ≥ 2. Важным следствием основного результата работы является полиномиальная разрешимость задачи распознавания Gϵ Lm(3) в классе расщепляемых графов.

 

Об авторе

Т. В. Лубашева
Белорусский государственный экономический университет
Беларусь

Лубашева Татьяна Владимировна – ассистент.

Пр. Партизанский, 26, 220070, Минск



Список литературы

1. Лубашева, Т. В. Характеризация и распознавание графов пересечений ребер 3-хроматических гиперграфов кратности не выше 2 в классе расщепляемых графов / Т. В. Лубашева, Ю. М. Метельский // Журнал Бел. гос. ун-та. Математика. Информатика. - 2017. - № 3. - С. 94-99.

2. Berge, C. Hypergraphs. Combinatorics of Finite Sets / C. Berge. - Amsterdam, New-York, Oxford, Tokyo : North-Holland, 1989. - 528 p.

3. Tyshkevich, R. I. Matroidal decomposition of graph / R. I. Tyshkevich, O. P. Urbanovich, I. E. Zverovich // Combinatorics and Graph Theory. - 1989. - Vol. 25. - P. 195-205.

4. Тышкевич, Р. И. Графы с матроидным числом 2 / Р. И. Тышкевич, О. П. Урбанович // Весщ АН БССР. Cер. фгз.-мат. навук. - 1989. - № 3. - C. 13-17.

5. Метельский, Ю. М. Пересечения матроидов и реберные гиперграфы / Ю. М. Метельский, Р. И. Тышкевич // Тр. Ин-та математики НАН Беларуси. - 2005. - Т. 13, № 2. - C. 44-54.

6. Harary, F. Line graphs of bipartite graphs / F. Harary, C. Holzmann // Rev. Soc. Mat. Chile. - 1974. - Vol. 1. -P. 19-22.

7. Тышкевич, Р. И. Каноническое разложение графа, определяемого степенями его вершин / Р. И. Тышкевич, А. А. Черняк // Известия АН БССР. Сер. физ.-мат. наук. - 1979. - Т. 5. - C. 14-26.

8. Foldes, S. Congressus numerantium / S. Foldes, P. L. Hammer // Winnipeg: Utilitas Math. - 1977. - Vol. XIX. -P. 311-315.

9. Foldes, S. Split graphs having Dilworth number two / S. Foldes, P. L. Hammer // Canadian Journal of Mathematics. -1977. - Vol. 29, iss. 3. - Р. 666-672.

10. Бабайцев, А. Ю. Линейная размерность расщепляемых графов / А. Ю. Бабайцев, Р. И. Тышкевич // Вес. Нац. акад. навук Беларуси Сер. фгз.-тэхн. навук. - 1999. - № 1. - C. 112-115.

11. Еськов, В. В. К характеризации реберных графов линейных гиперграфов при дополнительных ограничениях / В. В. Еськов, Р. И. Тышкевич // Вес. Нац. акад. навук Беларуси Сер. фгз.-тэхн. навук. - 2001. - № 2. -C. 122-126.

12. Лубашева, Т. В. О конечной характеризуемости графов с ограниченным числом эквивалентного разбиения в классах полярных графов / Т. В. Лубашева, Ю. М. Метельский // Тр. Ин-та математики НАН Беларуси. - 2011. -Т. 19, № 1. - С. 85-91.

13. Лубашева, Т. В. Характеризация графов с ограниченным сверху числом эквивалентного разбиения в классе U-расщепляемых графов / Т. В. Лубашева, Ю. М. Метельский // Тр. Ин-та математики НАН Беларуси. -2007. - Т. 15, № 1. - С. 91-97.

14. Тышкевич, Р. И. Декомпозиция графов / Р. И. Тышкевич, А. А. Черняк // Кибернетика. - 1985. - № 2. -C. 67-74.


Для цитирования:


Лубашева Т.В. Характеризация и распознавание графов пересечений ребер трихроматических гиперграфов ограниченной кратности в классе расщепляемых графов. Информатика. 2018;15(4):102-108.

For citation:


Lubasheva T.V. Characterization and recognition of edge intersection graphs of trichromatic hypergraphs with finite multiplicity in the class of split graphs. Informatics. 2018;15(4):102-108. (In Russ.)

Просмотров: 156


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)