| dbo:abstract |
The graph realization problem is a decision problem in graph theory. Given a finite sequence of natural numbers, the problem asks whether there is a labeled simple graph such that is the degree sequence of this graph. (en) Le problème de réalisation de graphe est un problème algorithmique. Étant donnée une liste de nombres entiers, il consiste à décider s'il existe un graphe dont la liste des degrés est égale à la liste donnée en entrée. (fr) Задача о реализации графа — задача разрешимости в теории графов. Задана конечная последовательность натуральных чисел, задача спрашивает, существует ли такой простой граф, в котором — последовательность степеней вершин этого графа. (ru) |
| dbo:wikiPageID |
43304622 (xsd:integer) |
| dbo:wikiPageLength |
3458 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1082745440 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Regular_graph dbr:Decision_problem dbr:Degree_sequence dbr:Symmetric_matrix dbr:Graph_(discrete_mathematics) dbr:Erdős–Gallai_theorem dbr:Havel–Hakimi_algorithm dbr:Adjacency_matrix dbr:Digraph_realization_problem dbr:Directed_graph dbr:Graph_theory dbr:Bipartite_graph dbr:Bipartite_realization_problem dbc:Computational_problems_in_graph_theory dbr:Polynomial-time_approximation_scheme dbr:Polynomial_time dbr:Recursion_(computer_science) |
| dbp:wikiPageUsesTemplate |
dbt:Reflist dbt:Short_description |
| dct:subject |
dbc:Computational_problems_in_graph_theory |
| rdfs:comment |
The graph realization problem is a decision problem in graph theory. Given a finite sequence of natural numbers, the problem asks whether there is a labeled simple graph such that is the degree sequence of this graph. (en) Le problème de réalisation de graphe est un problème algorithmique. Étant donnée une liste de nombres entiers, il consiste à décider s'il existe un graphe dont la liste des degrés est égale à la liste donnée en entrée. (fr) Задача о реализации графа — задача разрешимости в теории графов. Задана конечная последовательность натуральных чисел, задача спрашивает, существует ли такой простой граф, в котором — последовательность степеней вершин этого графа. (ru) |
| rdfs:label |
Problème de réalisation de graphe (fr) Graph realization problem (en) Задача о реализации графа (ru) |
| owl:sameAs |
freebase:Graph realization problem yago-res:Graph realization problem wikidata:Graph realization problem dbpedia-fr:Graph realization problem dbpedia-ru:Graph realization problem https://global.dbpedia.org/id/kmVe |
| prov:wasDerivedFrom |
wikipedia-en:Graph_realization_problem?oldid=1082745440&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-en:Graph_realization_problem |
| is dbo:wikiPageRedirects of |
dbr:Graph_realizability |
| is dbo:wikiPageWikiLink of |
dbr:Degree_(graph_theory) dbr:Erdős–Gallai_theorem dbr:Havel–Hakimi_algorithm dbr:Digraph_realization_problem dbr:Graph_flattenability dbr:Bipartite_realization_problem dbr:Graph_realizability |
| is foaf:primaryTopic of |
wikipedia-en:Graph_realization_problem |