This HTML5 document contains 99 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
n15http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
dbpedia-eshttp://es.dbpedia.org/resource/
n14https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
dbpedia-ruhttp://ru.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-srhttp://sr.dbpedia.org/resource/
n9http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-vihttp://vi.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Blossom_algorithm
rdf:type
yago:YagoGeoEntity yago:YagoPermanentlyLocatedEntity yago:WikicatRivers yago:PhysicalEntity100001930 yago:Stream109448361 yago:BodyOfWater109225146 yago:Lake109328904 dbo:Software yago:WikicatLakes yago:River109411430 yago:Thing100002452
rdfs:label
Algorithme d'Edmonds pour les couplages Blossom algorithm Algoritmo de Emparejamiento de Edmonds Алгоритм сжатия цветков
rdfs:comment
In graph theory, the blossom algorithm is an algorithm for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961, and published in 1965. Given a general graph G = (V, E), the algorithm finds a matching M such that each vertex in V is incident with at most one edge in M and |M| is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike bipartite matching, the key new idea is that an odd-length cycle in the graph (blossom) is contracted to a single vertex, with the search continuing iteratively in the contracted graph. En informatique, plus précisément en théorie des graphes, l'algorithme d'Edmonds pour les couplages (blossom algorithm en anglais), aussi connu sous le nom d'algorithme des fleurs et des pétales est un algorithme pour construire des couplages maximaux sur les graphes. L'algorithme a été développé par Jack Edmonds en 1961, et publié en 1965. Étant donné un graphe quelconque G = (V, E), l'algorithme trouve un couplage M tel que chaque sommet de V est incident à au plus une arête dans E et M est de cardinal maximal. Le couplage est construit en améliorant itérativement un couplage vide initial le long de chemins augmentant dans le graphe. Contrairement au couplage biparti, ce couplage se base sur l'idée qu'un cycle de longueur impaire dans le graphe (fleur) est contracté en un seul sommet, la El Algoritmo del Blossom o Algoritmo de Emparejamiento de Edmonds es un algoritmo de teoría de grafos para construir emparejamientos máximos en grafos. El algoritmo fue desarrollado por Jack Edmonds en 1961,​ y publicado en 1965.​ El emparejamiento máximo es construido iterativamente mejorando el emparejamiento actual a través de caminos m-incrementos mientras al menos exista uno. La idea esencial del algoritmo es que un ciclo de longitud impar (blossom) es contraído en un solo vértice para luego continuar la búsqueda de caminos m-incrementos en el grafo resultante. La idea de contraer los ciclos de longitud impar se debe a que si no se hiciera el mismo algoritmo de búsqueda de caminos m-incrementos al entrar en uno de estos ciclos y salir pudiera reportar falsos positivos. Алгоритм сжатия цветков (англ. Blossom algorithm) — алгоритм в теории графов для построения наибольших паросочетаний на графах. Алгоритм разработал Джек Эдмондс в 1961 году и опубликовал в 1965 году. Если дан граф G=(V, E) общего вида, алгоритм находит паросочетание M такое, что каждая вершина из V инцидентна не более чем одному ребру из M и |M| максимально. Паросочетание строится путём итеративного улучшения начального пустого паросочетания вдоль увеличивающих путей графа. В отличие от двудольного паросочетания ключевой новой идеей было сжатие нечётного цикла в графе (цветка) в одну вершину с продолжением поиска итеративно по сжатому графу.
foaf:depiction
n9:Path_detection.png n9:Edmonds_lifting_path.svg n9:Path_lifting.png n9:Edmonds_blossom.svg n9:Edmonds_lifting_end_point.svg n9:Edmonds_augmenting_path.svg n9:Forest_expansion.png n9:Blossom_contraction.png
dcterms:subject
dbc:Graph_algorithms dbc:Matching_(graph_theory)
dbo:wikiPageID
24277294
dbo:wikiPageRevisionID
1111919935
dbo:wikiPageWikiLink
dbr:Vertex_(graph) dbr:Polytope dbr:Maximum_weight_matching dbr:If_and_only_if dbr:Graph_(discrete_mathematics) n15:Edmonds_augmenting_path.svg n15:Edmonds_blossom.svg dbc:Graph_algorithms n15:Edmonds_lifting_end_point.svg n15:Edmonds_lifting_path.svg dbr:Bipartite_graph dbr:Algorithm dbr:Edge_(graph) dbr:Blossom_(graph_theory) dbr:Polyhedral_combinatorics n15:Path_detection.png n15:Path_lifting.png dbr:Alexander_Schrijver dbr:Edge_contraction n15:Forest_expansion.png dbr:Big_O_notation dbc:Matching_(graph_theory) n15:Blossom_contraction.png dbr:Ford–Fulkerson_algorithm dbr:Forest_(graph_theory) dbr:Linear_programming dbr:Total_unimodularity dbr:Jack_Edmonds dbr:Maximum_matching dbr:Graph_theory dbr:Berge's_lemma
owl:sameAs
dbpedia-ru:Алгоритм_сжатия_цветков wikidata:Q1030529 yago-res:Blossom_algorithm n14:7QKK dbpedia-fa:الگوریتم_شکوفه_ادموندز dbpedia-sr:Алгоритам_максималног_упаривања dbpedia-fr:Algorithme_d'Edmonds_pour_les_couplages freebase:m.07sb36l dbpedia-vi:Thuật_toán_ghép_cặp_của_Edmonds dbpedia-es:Algoritmo_de_Emparejamiento_de_Edmonds
dbp:wikiPageUsesTemplate
dbt:Abs dbt:Mvar dbt:Math dbt:Sub dbt:Code dbt:Sup dbt:Short_description
dbo:thumbnail
n9:Edmonds_augmenting_path.svg?width=300
dbo:abstract
En informatique, plus précisément en théorie des graphes, l'algorithme d'Edmonds pour les couplages (blossom algorithm en anglais), aussi connu sous le nom d'algorithme des fleurs et des pétales est un algorithme pour construire des couplages maximaux sur les graphes. L'algorithme a été développé par Jack Edmonds en 1961, et publié en 1965. Étant donné un graphe quelconque G = (V, E), l'algorithme trouve un couplage M tel que chaque sommet de V est incident à au plus une arête dans E et M est de cardinal maximal. Le couplage est construit en améliorant itérativement un couplage vide initial le long de chemins augmentant dans le graphe. Contrairement au couplage biparti, ce couplage se base sur l'idée qu'un cycle de longueur impaire dans le graphe (fleur) est contracté en un seul sommet, la recherche se poursuivant de manière itérative dans le graphe contracté. L'algorithme a une complexité temporelle en , où est le nombre d'arêtes du graphe et est son nombre de sommets. L'algorithme de Micali et Vazirani permet de résoudre le même problème en , cependant il est beaucoup plus compliqué. Le blossom algorithm est historiquement important car il a donné la première preuve qu'un couplage maximal pouvait être trouvé en un temps polynomial, ce qui prouve que le problème de couplage maximal est dans la classe de complexité P. In graph theory, the blossom algorithm is an algorithm for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961, and published in 1965. Given a general graph G = (V, E), the algorithm finds a matching M such that each vertex in V is incident with at most one edge in M and |M| is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike bipartite matching, the key new idea is that an odd-length cycle in the graph (blossom) is contracted to a single vertex, with the search continuing iteratively in the contracted graph. The algorithm runs in time O(|E||V|2), where |E| is the number of edges of the graph and |V| is its number of vertices. A better running time of for the same task can be achieved with the much more complex algorithm of Micali and Vazirani. A major reason that the blossom algorithm is important is that it gave the first proof that a maximum-size matching could be found using a polynomial amount of computation time. Another reason is that it led to a linear programming polyhedral description of the matching polytope, yielding an algorithm for min-weight matching. As elaborated by Alexander Schrijver, further significance of the result comes from the fact that this was the first polytope whose proof of integrality "does not simply follow just from total unimodularity, and its description was a breakthrough in polyhedral combinatorics." El Algoritmo del Blossom o Algoritmo de Emparejamiento de Edmonds es un algoritmo de teoría de grafos para construir emparejamientos máximos en grafos. El algoritmo fue desarrollado por Jack Edmonds en 1961,​ y publicado en 1965.​ El emparejamiento máximo es construido iterativamente mejorando el emparejamiento actual a través de caminos m-incrementos mientras al menos exista uno. La idea esencial del algoritmo es que un ciclo de longitud impar (blossom) es contraído en un solo vértice para luego continuar la búsqueda de caminos m-incrementos en el grafo resultante. La idea de contraer los ciclos de longitud impar se debe a que si no se hiciera el mismo algoritmo de búsqueda de caminos m-incrementos al entrar en uno de estos ciclos y salir pudiera reportar falsos positivos. La importancia del algoritmo radicó en que dio la primera prueba de que un emparejamiento máximo puede ser encontrado en tiempo polinomial. Алгоритм сжатия цветков (англ. Blossom algorithm) — алгоритм в теории графов для построения наибольших паросочетаний на графах. Алгоритм разработал Джек Эдмондс в 1961 году и опубликовал в 1965 году. Если дан граф G=(V, E) общего вида, алгоритм находит паросочетание M такое, что каждая вершина из V инцидентна не более чем одному ребру из M и |M| максимально. Паросочетание строится путём итеративного улучшения начального пустого паросочетания вдоль увеличивающих путей графа. В отличие от двудольного паросочетания ключевой новой идеей было сжатие нечётного цикла в графе (цветка) в одну вершину с продолжением поиска итеративно по сжатому графу. Основной причиной, почему алгоритм сжатия цветков важен, является то, что он дал первое доказательство возможности нахождения наибольшего паросочетания за полиномиальное время. Другой причиной является то, что метод приводит к описанию многогранника линейного программирования для многогранника паросочетаний, что приводит к алгоритму паросочетания минимального веса.Как уточнил Александр Схрейвер, дальнейшая важность результата следует из факта, что этот многогранник был первым, доказательство целочисленности которого «не просто следовало из тотальной унимодулярности, а его описание было прорывом в комбинаторике многогранников».
gold:hypernym
dbr:Algorithm
prov:wasDerivedFrom
wikipedia-en:Blossom_algorithm?oldid=1111919935&ns=0
dbo:wikiPageLength
16965
foaf:isPrimaryTopicOf
wikipedia-en:Blossom_algorithm
Subject Item
dbr:University_of_Waterloo
dbo:wikiPageWikiLink
dbr:Blossom_algorithm
Subject Item
dbr:Dulmage–Mendelsohn_decomposition
dbo:wikiPageWikiLink
dbr:Blossom_algorithm
Subject Item
dbr:Integral_polytope
dbo:wikiPageWikiLink
dbr:Blossom_algorithm
Subject Item
dbr:Maximum_cardinality_matching
dbo:wikiPageWikiLink
dbr:Blossom_algorithm
Subject Item
dbr:Claw-free_graph
dbo:wikiPageWikiLink
dbr:Blossom_algorithm
Subject Item
dbr:Gallai–Edmonds_decomposition
dbo:wikiPageWikiLink
dbr:Blossom_algorithm
Subject Item
dbr:Jack_Edmonds
dbo:wikiPageWikiLink
dbr:Blossom_algorithm
dbo:knownFor
dbr:Blossom_algorithm
Subject Item
dbr:Edmonds's_matching_algorithm
dbo:wikiPageWikiLink
dbr:Blossom_algorithm
dbo:wikiPageRedirects
dbr:Blossom_algorithm
Subject Item
wikipedia-en:Blossom_algorithm
foaf:primaryTopic
dbr:Blossom_algorithm