An Entity of Type: WikicatTheoremsInGraphTheory, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

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
dbo:wikiPageID
  • 30208106 (xsd:integer)
dbo:wikiPageLength
  • 8999 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1087229484 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
gold:hypernym
rdf:type
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
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License