Berge's theorem (original) (raw)
En teoria de grafs, el lema de Berge és un lema demostrat pel matemàtic francès el 1957, que diu el següent: Un aparellament és màxim si conté el major nombre d'arestes possibles. Una ruta augmentativa (en anglès augmenting path) és un camí que comença i acaba en vèrtexs lliures o no connectats, i alterna entre arestes que estan i no estan en l'aparellament.
| Property | Value |
|---|---|
| dbo:abstract | En teoria de grafs, el lema de Berge és un lema demostrat pel matemàtic francès el 1957, que diu el següent: Un aparellament és màxim si conté el major nombre d'arestes possibles. Una ruta augmentativa (en anglès augmenting path) és un camí que comença i acaba en vèrtexs lliures o no connectats, i alterna entre arestes que estan i no estan en l'aparellament. (ca) In graph theory, Berge's theorem states that a matching M in a graph G is maximum (contains the largest possible number of edges) if and only if there is no augmenting path (a path that starts and ends on free (unmatched) vertices, and alternates between edges in and not in the matching) with M. It was proven by French mathematician Claude Berge in 1957 (though already observed by Petersen in 1891 and Kőnig in 1931). (en) In der Graphentheorie, einem der Teilgebiete der Mathematik, ist der Satz von Berge einer von mehreren Sätzen, die auf den französischen Mathematiker Claude Berge (1926–2002) zurückgehen. Berge publizierte den Satz im Jahre 1957 und gab damit eine Charakterisierung größtmöglicher Matchings in endlichen Graphen. In dieser Publikation gab Berge auch einen Algorithmus zur Bestimmung eines solchen Matchings. (de) En teoría de grafos, el Lema de Berge es un lema demostrado por el matemático francés Claude Berge en 1957, que dice lo siguiente: Un matching es máximo si contiene el mayor número de aristas posibles. Una ruta aumentativa (augmenting path) es un camino que comienza y termina en vértices libres o no conectados, y alterna entre aristas que están y no están en el matching. (es) En théorie des graphes, le lemme de Berge est le suivant : Lemme de Berge — Un couplage M dans un graphe G est maximum (c'est-à-dire contient le plus grand nombre d'arêtes possible) si et seulement s'il n'y a pas de chemin d'augmentation (un chemin qui commence et se termine sur des sommets libres (non couplés)), et qui alterne entre les arêtes dans et en dehors du couplage M. Ce lemme a été prouvé par le mathématicien français Claude Berge en 1957, bien qu'il ait déjà été observé par Julius Petersen en 1891 et par Dénes Kőnig en 1931. (fr) У теорії графів, лема Берже стверджує, що парування є найбільшим тоді і тільки тоді, якщо в немає шляхів розширення щодо (uk) Лемма Бержа утверждает, что паросочетание M в графе G является наибольшим (содержит наибольшее возможное число рёбер) тогда и только тогда, когда не существует дополняющего пути (пути, который начинается и завершается на свободных, то есть не принадлежащих паросочетаниям, вершинах и поочерёдно проходит по рёбрам, принадлежащим и не принадлежащим паросочетанию) в M. Лемму доказал французский математик в 1957 году (хотя её уже обсуждали Петерсен в 1891 и Кёниг в 1931). (ru) |
| dbo:wikiPageExternalLink | http://www.pnas.org/content/43/9/842.full.pdf |
| dbo:wikiPageID | 22577850 (xsd:integer) |
| dbo:wikiPageLength | 6449 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116015193 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cycle_(graph_theory) dbc:Matching_(graph_theory) dbr:Contrapositive dbr:Matching_(graph_theory) dbr:Claude_Berge dbr:Graph_(discrete_mathematics) dbr:Path_(graph_theory) dbr:Proceedings_of_the_National_Academy_of_Sciences_of_the_United_States_of_America dbr:Julius_Petersen dbr:Dénes_Kőnig dbr:France dbr:Graph_theory dbr:Lemma_(mathematics) dbr:Vertex_(graph_theory) dbr:Symmetric_difference |
| dbp:wikiPageUsesTemplate | dbt:About dbt:Citation |
| dcterms:subject | dbc:Matching_(graph_theory) |
| rdfs:comment | En teoria de grafs, el lema de Berge és un lema demostrat pel matemàtic francès el 1957, que diu el següent: Un aparellament és màxim si conté el major nombre d'arestes possibles. Una ruta augmentativa (en anglès augmenting path) és un camí que comença i acaba en vèrtexs lliures o no connectats, i alterna entre arestes que estan i no estan en l'aparellament. (ca) In graph theory, Berge's theorem states that a matching M in a graph G is maximum (contains the largest possible number of edges) if and only if there is no augmenting path (a path that starts and ends on free (unmatched) vertices, and alternates between edges in and not in the matching) with M. It was proven by French mathematician Claude Berge in 1957 (though already observed by Petersen in 1891 and Kőnig in 1931). (en) In der Graphentheorie, einem der Teilgebiete der Mathematik, ist der Satz von Berge einer von mehreren Sätzen, die auf den französischen Mathematiker Claude Berge (1926–2002) zurückgehen. Berge publizierte den Satz im Jahre 1957 und gab damit eine Charakterisierung größtmöglicher Matchings in endlichen Graphen. In dieser Publikation gab Berge auch einen Algorithmus zur Bestimmung eines solchen Matchings. (de) En teoría de grafos, el Lema de Berge es un lema demostrado por el matemático francés Claude Berge en 1957, que dice lo siguiente: Un matching es máximo si contiene el mayor número de aristas posibles. Una ruta aumentativa (augmenting path) es un camino que comienza y termina en vértices libres o no conectados, y alterna entre aristas que están y no están en el matching. (es) En théorie des graphes, le lemme de Berge est le suivant : Lemme de Berge — Un couplage M dans un graphe G est maximum (c'est-à-dire contient le plus grand nombre d'arêtes possible) si et seulement s'il n'y a pas de chemin d'augmentation (un chemin qui commence et se termine sur des sommets libres (non couplés)), et qui alterne entre les arêtes dans et en dehors du couplage M. Ce lemme a été prouvé par le mathématicien français Claude Berge en 1957, bien qu'il ait déjà été observé par Julius Petersen en 1891 et par Dénes Kőnig en 1931. (fr) У теорії графів, лема Берже стверджує, що парування є найбільшим тоді і тільки тоді, якщо в немає шляхів розширення щодо (uk) Лемма Бержа утверждает, что паросочетание M в графе G является наибольшим (содержит наибольшее возможное число рёбер) тогда и только тогда, когда не существует дополняющего пути (пути, который начинается и завершается на свободных, то есть не принадлежащих паросочетаниям, вершинах и поочерёдно проходит по рёбрам, принадлежащим и не принадлежащим паросочетанию) в M. Лемму доказал французский математик в 1957 году (хотя её уже обсуждали Петерсен в 1891 и Кёниг в 1931). (ru) |
| rdfs:label | Lema de Berge (ca) Satz von Berge (de) Berge's theorem (en) Lema de Berge (es) Lemme de Berge (fr) Лемма Бержа (ru) Лема Берже (uk) |
| owl:sameAs | wikidata:Berge's theorem dbpedia-ca:Berge's theorem dbpedia-de:Berge's theorem dbpedia-es:Berge's theorem dbpedia-fa:Berge's theorem dbpedia-fr:Berge's theorem dbpedia-ru:Berge's theorem dbpedia-uk:Berge's theorem https://global.dbpedia.org/id/4jKQk |
| prov:wasDerivedFrom | wikipedia-en:Berge's_theorem?oldid=1116015193&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Berge's_theorem |
| is dbo:wikiPageRedirects of | dbr:Berge's_lemma dbr:Augmenting_path_theorem |
| is dbo:wikiPageWikiLink of | dbr:Berge's_lemma dbr:Augmenting_path_theorem dbr:Ford–Fulkerson_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Berge's_theorem |