Drevesna širina : delo diplomskega seminarja

Gruber, Milka (author), Iršič, Vesna (mentor)

Diplomsko delo obravnava drevesno širino, to je lastnost grafa, ki meri njegovo podobnost drevesu in je zelo uporabna z algoritmičnega vidika. Kanonična definicija drevesne širine sloni na konceptu drevesne dekompozicije grafa, to je način razdelitve grafa v podmnožice vozlišč, ki so strukturirane v drevo. Na grafih, za katere obstajajo drevesne dekompozicije z majhnimi deli, lahko učinkovito rešimo nekatere NP-polne optimizacijske probleme.

• Language: Slovenian
• Keywords: teorija grafov, graf, drevo, drevesna širina, drevesna dekompozicija, robidnica, robidno število, problem maksimalne neodvisne utežene množice
• Work type: Final seminar paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2024
• PID: 20.500.12556/RUL-162135
• UDC: 519.17
• COBISS.SI-ID: 208488963
• Publication date in RUL: 19.09.2024

Secondary language

• Language: English
• Title: Treewidth

Abstract

We present the concept of treewidth, a graph property that measures its similarity to a tree and is very useful from an algorithmic perspective. The canonical definition of treewidth, is based on the concept of a tree decomposition of a graph, which is a method of partitioning the graph into subsets of vertices that are structured as a tree. For graphs that have tree decompositions with small parts, some NP-hard optimization problems can be solved efficiently.

• Keywords: graph theory, graph, tree, treewidth, tree decomposition, bramble, bramble number, maximum weighted independent set problem