Abstract: Cut problems in graph theory are extensively studied and well understood. However, cuts that partition graphs into components that are connected in a prescribed way, have received comparatively less attention. In this thesis, we formally define several connected cut problems, focusing on Minimum \(k\)-connected cut and Minimum \(k\)-connected cut with source problems. Given a graph \(G=(V,E)\), and an interger \(k\), the goal is to partition a vertex set \(V\) into two subsets, \(S\) and \(V \setminus S\), such that the induced subgraph \(G[S]\) is connected, the size of \(S\) is exactly \(k\), and the number of edges between \(S\) and \(V \setminus S\) is minimized. In the second problem, we are in addition given a source vertex \(s\in V\) that has to be included in \(S\). Our first result is a proof that both Minimum \(k\)-connected cut and Minimum \(k\)-connected cut with source problems are NP-complete. Additionally, we propose a bicriteria approximation algorithm for the Minimum \(k\)-connected cut with source problem. As a result, we also obtain a bicriteria approximation for the general Minimum \(k\)-connected cut problem.
Presentation and Handouts
Abstract: This thesis describes the development of a desktop application that should allow the user to organize their family tree. The existing solutions, such as MyHeritage or Family Historian, are analyzed first. The detailed specification of the program itself is subsequently performed, covering the list of requirements, processes, individual entities, and the solution concept. We conclude with the documentation of the already implemented program, which contains programming and installation documentation as well as the user manual.
Dobré poznámky má také Tomáš Sláma
Některé odkazy lze najít na Matfyzácké wiki