Операцiя перемикання Зейделя на неорiєнтованих графах

Loading...
Thumbnail Image
Date
2021
Authors
Лозовой, Олексій
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Операцiя перемикання була запропонована Зейделем та ван Лiнтом у їх спiльнiй роботi по елiптичнiй геометрiї. Її суть полягає в тому, щоб взати певну вершину графу, прибрати всi ребра, якi вона має, а також додати ребра мiж тими вершинами, з якими вона не була сумiжна. Цей граф i буде перемиканням даного по вершинi. В одночас Зейделем було виявлено зв’язок мiж класами перемикань та так званими два-графами. Потiм дослiдженням класiв перемиканнь, зокрема питання циклiчностi графiв у класах, займався Хейдж. Пiзнiше, у 2015, Козеренко дослiдив властивостi так званих s-максимальних графiв. Це такi графи, кiлькiсть ребер яких, найбiльша серед усiх, в його класi перемикань.
Description
Keywords
операція перемикання, s-максимальні графи, алгоритм, перемикання Зейделя, еквівалентність класам перемикань, бакалаврська робота
Citation