Козеренко, СергійРоманчук, Богдан2024-04-032024-04-032023https://ekmair.ukma.edu.ua/handle/123456789/28588Нехай 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 орграфи.ukобхiд сторожачисло сторожаповнi мультичастковi графиорграфибакалаврська роботаПроблема обходу сторожа на графах i орграфахOther