Home > Search Results: keywords:"minimální protipříklad"
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 2 records found  Search took 0.01 seconds. 
Minimal counterexamples to flow conjectures
 Korcsok, Peter ; Šámal, Robert (advisor) ; Goodall, Andrew (referee)
We say that a~graph admits a~nowhere-zero k-flow if we can assign a~direction and a~positive integer (<k) as a~flow to each edge so that total in-flow into $v$ and total out-flow from $v$ are equal for each vertex $v$. In 1954, Tutte conjectured that every bridgeless graph admits a~nowhere-zero 5-flow and the conjecture is still open. Kochol in his recent papers introduces a~computational method how to prove that a~minimal counterexample cannot contain short circuits (up to length 10). In this Thesis, we provide a~comprehensive view on this method. Moreover, since Kochol does not share his implementation and in order to independently verify the method, we provide our source code that validates Kochol's results and extend them: we prove that any minimal counterexample to the conjecture does not contain any circuit of length less than 12. Powered by TCPDF (www.tcpdf.org)
Detailed record
Minimal counterexamples to flow conjectures
 Korcsok, Peter ; Šámal, Robert (advisor) ; Goodall, Andrew (referee)
We say that a~graph admits a~nowhere-zero k-flow if we can assign a~direction and a~positive integer (<k) as a~flow to each edge so that total in-flow into $v$ and total out-flow from $v$ are equal for each vertex $v$. In 1954, Tutte conjectured that every bridgeless graph admits a~nowhere-zero 5-flow and the conjecture is still open. Kochol in his recent papers introduces a~computational method how to prove that a~minimal counterexample cannot contain short circuits (up to length 10). In this Thesis, we provide a~comprehensive view on this method. Moreover, since Kochol does not share his implementation and in order to independently verify the method, we provide our source code that validates Kochol's results and extend them: we prove that any minimal counterexample to the conjecture does not contain any circuit of length less than 12. Powered by TCPDF (www.tcpdf.org)
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English