Erdős–Gallai theorem (original) (raw)
The Erdős–Gallai theorem is a result in graph theory, a branch of combinatorial mathematics. It provides one of two known approaches to solving the graph realization problem, i.e. it gives a necessary and sufficient condition for a finite sequence of natural numbers to be the degree sequence of a simple graph. A sequence obeying these conditions is called "graphic". The theorem was published in 1960 by Paul Erdős and Tibor Gallai, after whom it is named.
| Property | Value |
|---|---|
| dbo:abstract | The Erdős–Gallai theorem is a result in graph theory, a branch of combinatorial mathematics. It provides one of two known approaches to solving the graph realization problem, i.e. it gives a necessary and sufficient condition for a finite sequence of natural numbers to be the degree sequence of a simple graph. A sequence obeying these conditions is called "graphic". The theorem was published in 1960 by Paul Erdős and Tibor Gallai, after whom it is named. (en) De stelling van Erdős en Gallai is een stelling uit de grafentheorie. Ze geeft noodzakelijke en voldoende voorwaarden opdat met een eindige lijst van natuurlijke getallen een enkelvoudige, niet-gerichte graaf kan gemaakt worden, waarvan de graden van de knopen overeenstemmen met de getallen in de lijst. Dergelijke lijst, gerangschikt in niet-stijgende volgorde, noemt men een "grafische lijst". Een graaf met overeenstemmende graden noemt men een realisatie van de lijst. Niet elke willekeurige lijst van natuurlijke getallen is een grafische lijst. Zo moet om te beginnen de som van de getallen in de lijst even zijn: elke zijde wordt immers tweemaal geteld, eenmaal bij de beginknoop en eenmaal bij de eindknoop. De stelling werd in 1960 gepubliceerd door Paul Erdős en Tibor Gallai in een Hongaars tijdschrift. (nl) Теорема Эрдёша — Галлаи (критерий Эрдёша — Галлаи) — утверждение в теории графов, задающее условие, при котором конечной последовательности натуральных чисел можно сопоставить степени вершин некоторого графа.Такие последовательности чисел называются графическими. Теорема доказана венгерскими математиками Палом Эрдёшем и (венг. Gallai Tibor) в 1960 году. (ru) |
| dbo:wikiPageExternalLink | http://www.renyi.hu/~p_erdos/1961-05.pdf http://www.math.uiuc.edu/~west/pubs/tripathi.ps |
| dbo:wikiPageID | 30208106 (xsd:integer) |
| dbo:wikiPageLength | 8999 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1087229484 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Paul_Erdős dbr:Degree_(graph_theory) dbr:Double_counting_(proof_technique) dbr:Mathematical_induction dbr:Claude_Berge dbr:Elsevier dbr:Combinatorics dbr:Fulkerson–Chen–Anstee_theorem dbr:Majorization dbr:Prefix_sum dbr:Tibor_Gallai dbr:Gale–Ryser_theorem dbr:Havel–Hakimi_algorithm dbr:Lattice_(order) dbr:Flow_network dbr:Partition_(number_theory) dbr:Discrete_Mathematics_(journal) dbr:Graph_realization_problem dbr:Graph_theory dbc:Theorems_in_graph_theory dbr:Handshaking_lemma dbr:Ferrers_diagram dbc:Paul_Erdős dbr:Integer dbr:Natural_number dbr:Simple_graph dbr:Finite_sequence dbr:Bridges_of_Königsberg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harv dbt:Harvtxt dbt:Short_description |
| dct:subject | dbc:Theorems_in_graph_theory dbc:Paul_Erdős |
| gold:hypernym | dbr:Result |
| rdf:type | yago:WikicatMathematicalTheorems yago:WikicatTheoremsInGraphTheory yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | The Erdős–Gallai theorem is a result in graph theory, a branch of combinatorial mathematics. It provides one of two known approaches to solving the graph realization problem, i.e. it gives a necessary and sufficient condition for a finite sequence of natural numbers to be the degree sequence of a simple graph. A sequence obeying these conditions is called "graphic". The theorem was published in 1960 by Paul Erdős and Tibor Gallai, after whom it is named. (en) Теорема Эрдёша — Галлаи (критерий Эрдёша — Галлаи) — утверждение в теории графов, задающее условие, при котором конечной последовательности натуральных чисел можно сопоставить степени вершин некоторого графа.Такие последовательности чисел называются графическими. Теорема доказана венгерскими математиками Палом Эрдёшем и (венг. Gallai Tibor) в 1960 году. (ru) De stelling van Erdős en Gallai is een stelling uit de grafentheorie. Ze geeft noodzakelijke en voldoende voorwaarden opdat met een eindige lijst van natuurlijke getallen een enkelvoudige, niet-gerichte graaf kan gemaakt worden, waarvan de graden van de knopen overeenstemmen met de getallen in de lijst. Dergelijke lijst, gerangschikt in niet-stijgende volgorde, noemt men een "grafische lijst". Een graaf met overeenstemmende graden noemt men een realisatie van de lijst. De stelling werd in 1960 gepubliceerd door Paul Erdős en Tibor Gallai in een Hongaars tijdschrift. (nl) |
| rdfs:label | Erdős–Gallai theorem (en) Stelling van Erdős en Gallai (nl) Теорема Эрдёша — Галлаи (ru) |
| owl:sameAs | freebase:Erdős–Gallai theorem wikidata:Erdős–Gallai theorem dbpedia-nl:Erdős–Gallai theorem dbpedia-ru:Erdős–Gallai theorem https://global.dbpedia.org/id/4jy7w |
| prov:wasDerivedFrom | wikipedia-en:Erdős–Gallai_theorem?oldid=1087229484&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Erdős–Gallai_theorem |
| is dbo:wikiPageRedirects of | dbr:Erdos-Gallai_theorem dbr:Erdos–Gallai_theorem dbr:Erdős-Gallai_theorem |
| is dbo:wikiPageWikiLink of | dbr:Degree_(graph_theory) dbr:Douglas_West_(mathematician) dbr:List_of_scientific_laws_named_after_people dbr:Fulkerson–Chen–Anstee_theorem dbr:Tibor_Gallai dbr:Gale–Ryser_theorem dbr:Havel–Hakimi_algorithm dbr:Erdos-Gallai_theorem dbr:Graph_realization_problem dbr:Erdos–Gallai_theorem dbr:Erdős-Gallai_theorem dbr:Eberhard's_theorem dbr:List_of_theorems dbr:List_of_things_named_after_Paul_Erdős |
| is foaf:primaryTopic of | wikipedia-en:Erdős–Gallai_theorem |