The Havel–Hakimi algorithm is an algorithm in graph theory solving the graph realization problem. That is, it answers the following question: Given a finite list of nonnegative integers in non-increasing order, is there a simple graph such that its degree sequence is exactly this list? A simple graph contains no double edges or loops. The degree sequence is a list of numbers in nonincreasing order indicating the number of edges incident to each vertex in the graph. If a simple graph exists for exactly the given degree sequence, the list of integers is called graphic. The Havel-Hakimi algorithm constructs a special solution if a simple graph for the given degree sequence exists, or proves that one cannot find a positive answer. This construction is based on a recursive algorithm. The algori
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Havlův algoritmus (cs)
- Havel-Hakimi-Algorithmus (de)
- Havel–Hakimi algorithm (en)
- Algorithme de Havel-Hakimi (fr)
- Алгоритм Гавела — Хакими (ru)
- 哈韦尔-哈基米算法 (zh)
|
| 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. Algoritmus byl poprvé zveřejněn v roce 1955 českým matematikem Václavem Havlem. V roce 1962 stejný algoritmus zveřejnil i . (cs)
- Der Havel-Hakimi-Algorithmus (oder auch Verfahren nach Havel-Hakimi) ist ein Verfahren aus der Graphentheorie, mit dem die Existenz eines einfachen Graphen zu einer gegebenen Valenzsequenz bestimmt und konstruiert werden kann. Der Algorithmus basiert auf dem Havel-Hakimi Theorem. (de)
- En théorie des graphes, l'algorithme de Havel-Hakimi est un algorithme résolvant le problème de la réalisation d'un graphe, c'est-à-dire, étant donnée une liste d'entiers positifs ou nuls, déterminer s'il existe un graphe simple dont les degrés sont exactement cette liste. Si oui, la liste est dite graphique. L'algorithme construit un graphe solution s'il en existe un, ou prouve qu'il n'existe aucun. Cette construction est basée sur un algorithme récursif, publié par Havel en 1955 puis Hakimi en 1962. (fr)
- Алгоритм Гавела — Хакими — рекурсивный алгоритм позволяющий определить появляется ли данный список целых чисел как список всех валентностей некоторого конечного простого графа. При положительном ответе на этот вопрос список называется графическим. Алгоритм предложен в 1955 и переоткрыт в 1962. (ru)
- 哈韦尔-哈基米算法是一种图论算法，由)与)先后发表，解决了。这个问题是指给定一串有限多个非负整数组成的序列，是否存在一个简单图使得其恰为这个序列。我们称满足条件的序列为可简单图化的。如果一个序列可简单图化，这个算法能够构造一个特解；否则算法指出序列不可简单图化。该算法是一个递归算法。 (zh)
- The Havel–Hakimi algorithm is an algorithm in graph theory solving the graph realization problem. That is, it answers the following question: Given a finite list of nonnegative integers in non-increasing order, is there a simple graph such that its degree sequence is exactly this list? A simple graph contains no double edges or loops. The degree sequence is a list of numbers in nonincreasing order indicating the number of edges incident to each vertex in the graph. If a simple graph exists for exactly the given degree sequence, the list of integers is called graphic. The Havel-Hakimi algorithm constructs a special solution if a simple graph for the given degree sequence exists, or proves that one cannot find a positive answer. This construction is based on a recursive algorithm. The algori (en)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has 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 . (cs)
- Der Havel-Hakimi-Algorithmus (oder auch Verfahren nach Havel-Hakimi) ist ein Verfahren aus der Graphentheorie, mit dem die Existenz eines einfachen Graphen zu einer gegebenen Valenzsequenz bestimmt und konstruiert werden kann. Der Algorithmus basiert auf dem Havel-Hakimi Theorem. (de)
- The Havel–Hakimi algorithm is an algorithm in graph theory solving the graph realization problem. That is, it answers the following question: Given a finite list of nonnegative integers in non-increasing order, is there a simple graph such that its degree sequence is exactly this list? A simple graph contains no double edges or loops. The degree sequence is a list of numbers in nonincreasing order indicating the number of edges incident to each vertex in the graph. If a simple graph exists for exactly the given degree sequence, the list of integers is called graphic. The Havel-Hakimi algorithm constructs a special solution if a simple graph for the given degree sequence exists, or proves that one cannot find a positive answer. This construction is based on a recursive algorithm. The algorithm was published by , and later by . (en)
- En théorie des graphes, l'algorithme de Havel-Hakimi est un algorithme résolvant le problème de la réalisation d'un graphe, c'est-à-dire, étant donnée une liste d'entiers positifs ou nuls, déterminer s'il existe un graphe simple dont les degrés sont exactement cette liste. Si oui, la liste est dite graphique. L'algorithme construit un graphe solution s'il en existe un, ou prouve qu'il n'existe aucun. Cette construction est basée sur un algorithme récursif, publié par Havel en 1955 puis Hakimi en 1962. (fr)
- Алгоритм Гавела — Хакими — рекурсивный алгоритм позволяющий определить появляется ли данный список целых чисел как список всех валентностей некоторого конечного простого графа. При положительном ответе на этот вопрос список называется графическим. Алгоритм предложен в 1955 и переоткрыт в 1962. (ru)
- 哈韦尔-哈基米算法是一种图论算法，由)与)先后发表，解决了。这个问题是指给定一串有限多个非负整数组成的序列，是否存在一个简单图使得其恰为这个序列。我们称满足条件的序列为可简单图化的。如果一个序列可简单图化，这个算法能够构造一个特解；否则算法指出序列不可简单图化。该算法是一个递归算法。 (zh)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
![[RDF Data]](/fct/images/sw-rdf-blue.png)