Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/95148| Заглавие документа: | Неориентированные графы и конъюктивные нормальные формы, их задающие |
| Авторы: | Парака, И. А. |
| Тема: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика |
| Дата публикации: | 2013 |
| Издатель: | Минск: Изд. центр БГУ |
| Библиографическое описание источника: | Сборник работ 70-ой научной конференции студентов и аспирантов Белорусского государственного университета, 15–18 мая 2013 г., Минск: В 3 ч. Ч. 1 / Белорус. гос. ун-т.. - С. 222-226. |
| Аннотация: | В дискретной математике весьма важен алгоритм построения по конъюнктивной нормальной форме (КНФ) неориентированного графа (с обозначением его вершин 2-наборами). Его важность в том, что этот алгоритм доказывает полиномиальную сводимость проблемы ВЫП к проблеме m-клики. Естественно возникает вопрос о том, каждый ли неориентированный граф (неорграф), если его вершины обозначить аналогично, может быть построен по соответствующей КНФ. В данной статье показывается, что этот подход осуществить в общем случае невозможно, то есть описывается серия неориентированных графов, которые не могут быть заданы ни одной КНФ. |
| URI документа: | http://elib.bsu.by/handle/123456789/95148 |
| Регистрационный номер: | Деп. в БГУ 10.12.2013, № 002810122013 |
| Располагается в коллекциях: | 2013. Научная конференция студентов и аспирантов БГУ. Часть 1. |
Полный текст документа:
| Файл | Описание | Размер | Формат | |
|---|---|---|---|---|
| 222-226.pdf | 340,08 kB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.