Безпiковi функцiї на зв’язних графах
Loading...
Date
2023
Authors
Зимовець, Руслан
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Функцiю f на зв’язному графi G називають безпiковою, якщо для всiх впорядкованих трiйок рiзних вершин x, y, z кожного найкоротшого шляху графа буде виконуватись умова безпiковостi: f(y) ≤ max(f(x), f(y)) за рiвностi лише у випадку f(x) = f(y) = f(z). Цiллю даної роботи є детальне дослiдження властивостей безпiкових функцiй та розробка алгоритмiв для їх аналiзу. Також розглядається комбiнаторна задача пiдрахунку кiлькостi безпiкових функцiй на графах.
Description
Keywords
безпiкова функцiя, граф блокiв, опукла множина, цiлком опукла множина, множина рiвня функцiї, геодезичний вiдрiзок, Числа Белла, курсова робота