Проблема обходу сторожа на графах i орграфах
Loading...
Date
2023
Authors
Романчук, Богдан
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Нехай G – зв’язний неорiєнтований граф. Обходом сторожа на G називається мiнiмальний замкнений домiнуючий шлях. Довжину такого шляху позначають w(G) i називають числом сторожа. У цiй роботi ми розглядаємо обхiд сторожа на неорiєнтованих та орiєнтованих графах. Особливу увагу придiляємо повним мультичнастковим орграфам, даємо характеризацiю цьому класу графiв, а також знаходимо верхню оцiнку числа сторожа через домiнуюче число γ(D) i число незалежностi α(D). Позаяк метою цiєї роботи є дослiдження повних мультичасткових орграфiв, велику увагу придiлено статтi Даєра , що була опублiкована у 2021 роцi. У цiй статтi знайдена верхня оцiнка числа сторожа для турнiрiв, сформульовано i доведено ряд теорем про повнi мультичастковi орграфи.
Description
Keywords
обхiд сторожа, число сторожа, повнi мультичастковi графи, орграфи, бакалаврська робота