Havlův algoritmus (v zahraniční literatuře též Havel-Hakimi algoritmus) je algoritmus řešící jeden z problémů teorie grafů, totiž ověření, jestli pro konečný soubor nezáporných čísel existuje graf, pro který platí, že soubor stupňů jeho uzlů je permutace zadaného seznamu. Pokud takový graf existuje, nazveme soubor čísel kreslitelným a tento rekurzivní algoritmus ho dokáže najít a sestrojit. V opačném případě nám dává důkaz toho, že takový graf nemůže existovat.
| Property | Value |
|---|
| dbpedia-owl:abstract
|
- Havlův algoritmus (v zahraniční literatuře též Havel-Hakimi algoritmus) je algoritmus řešící jeden z problémů teorie grafů, totiž ověření, jestli pro konečný soubor nezáporných čísel existuje graf, pro který platí, že soubor stupňů jeho uzlů je permutace zadaného seznamu. Pokud takový graf existuje, nazveme soubor čísel kreslitelným a tento rekurzivní algoritmus ho dokáže najít a sestrojit. V opačném případě nám dává důkaz toho, že takový graf nemůže existovat. Algoritmus byl poprvé zveřejněn v roce 1955 českým matematikem Václavem Havlem. V roce 1962 stejný algoritmus zveřejnil i Hakimi.
|
| dbpedia-owl:wikiPageID
| |
| dbpedia-owl:wikiPageLength
| |
| dbpedia-owl:wikiPageOutDegree
| |
| dbpedia-owl:wikiPageRevisionID
| |
| dbpedia-owl:wikiPageWikiLink
| |
| dbpedia-owl:wikiPageWikiLinkText
|
- Havlova algoritmu
- Havlův algoritmus
|
| dcterms:subject
| |
| rdfs:comment
|
- Havlův algoritmus (v zahraniční literatuře též Havel-Hakimi algoritmus) je algoritmus řešící jeden z problémů teorie grafů, totiž ověření, jestli pro konečný soubor nezáporných čísel existuje graf, pro který platí, že soubor stupňů jeho uzlů je permutace zadaného seznamu. Pokud takový graf existuje, nazveme soubor čísel kreslitelným a tento rekurzivní algoritmus ho dokáže najít a sestrojit. V opačném případě nám dává důkaz toho, že takový graf nemůže existovat.
|
| rdfs:label
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbpedia-owl:wikiPageRedirects
of | |
| is dbpedia-owl:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
