Factor-critical graph (original) (raw)
In graph theory, a mathematical discipline, a factor-critical graph (or hypomatchable graph) is a graph with n vertices in which every subgraph of n − 1 vertices has a perfect matching. (A perfect matching in a graph is a subset of its edges with the property that each of its vertices is the endpoint of exactly one of the edges in the subset.) A matching that covers all but one vertex of a graph is called a near-perfect matching. So equivalently, a factor-critical graph is a graph in which there are near-perfect matchings that avoid every possible vertex.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, a mathematical discipline, a factor-critical graph (or hypomatchable graph) is a graph with n vertices in which every subgraph of n − 1 vertices has a perfect matching. (A perfect matching in a graph is a subset of its edges with the property that each of its vertices is the endpoint of exactly one of the edges in the subset.) A matching that covers all but one vertex of a graph is called a near-perfect matching. So equivalently, a factor-critical graph is a graph in which there are near-perfect matchings that avoid every possible vertex. (en) Фактор-критический граф (или почти сочетаемый граф .) — это граф с n вершинами, в котором каждый подграф с n − 1 вершинами имеет совершенное паросочетание. (Совершенное паросочетание в графе — это подмножество рёбер со свойством, что каждая из вершин графа является конечной вершиной в точности одного ребра из подмножества.) Сочетание, покрывающее все вершины, кроме одной, называется почти совершенным паросочетанием. Таким образом, эквивалентно, фактор-критический граф — это граф, в котором существуют почти совершенные паросочетания, которые не содержат любую из вершин. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Factor_critical.svg?width=300 |
| dbo:wikiPageID | 7684634 (xsd:integer) |
| dbo:wikiPageLength | 15720 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1065655054 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Mycielskian dbc:Graph_families dbr:Perfect_matching dbr:Regular_graph dbr:Regular_icosahedron dbr:Cycle_(graph_theory) dbr:Ear_decomposition dbc:Matching_(graph_theory) dbr:Complete_graph dbr:Connected_graph dbr:Friendship_graph dbr:Glossary_of_graph_theory dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:Critical_graph dbr:Linear_time dbr:László_Lovász dbr:Claw-free_graph dbr:Complement_graph dbr:Path_(graph_theory) dbr:Matching_polytope dbr:Matroid dbr:Tibor_Gallai dbr:K-edge-connected_graph dbr:K-vertex-connected_graph dbr:Cycle_graph dbr:Bridge_(graph_theory) dbr:Graph_theory dbr:Gyroelongated_pentagonal_pyramid dbr:Jack_Edmonds dbr:Bipartite_graph dbr:Edge_contraction dbr:Polyhedral_combinatorics dbr:Greedy_algorithm dbr:Grötzsch_graph dbr:Polynomial_time dbr:Maximum_matching dbr:Hamiltonian_cycle dbr:Minimal_element dbr:Edmonds's_matching_algorithm dbr:File:Friendship_graphs.svg dbr:File:Factor_critical.svg dbr:File:Gyroelongated_pentagonal_pyramid.png |
| dbp:wikiPageUsesTemplate | dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Graph_families dbc:Matching_(graph_theory) |
| gold:hypernym | dbr:Graph |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| rdfs:comment | In graph theory, a mathematical discipline, a factor-critical graph (or hypomatchable graph) is a graph with n vertices in which every subgraph of n − 1 vertices has a perfect matching. (A perfect matching in a graph is a subset of its edges with the property that each of its vertices is the endpoint of exactly one of the edges in the subset.) A matching that covers all but one vertex of a graph is called a near-perfect matching. So equivalently, a factor-critical graph is a graph in which there are near-perfect matchings that avoid every possible vertex. (en) Фактор-критический граф (или почти сочетаемый граф .) — это граф с n вершинами, в котором каждый подграф с n − 1 вершинами имеет совершенное паросочетание. (Совершенное паросочетание в графе — это подмножество рёбер со свойством, что каждая из вершин графа является конечной вершиной в точности одного ребра из подмножества.) Сочетание, покрывающее все вершины, кроме одной, называется почти совершенным паросочетанием. Таким образом, эквивалентно, фактор-критический граф — это граф, в котором существуют почти совершенные паросочетания, которые не содержат любую из вершин. (ru) |
| rdfs:label | Factor-critical graph (en) Фактор-критический граф (ru) |
| owl:sameAs | freebase:Factor-critical graph yago-res:Factor-critical graph wikidata:Factor-critical graph dbpedia-fa:Factor-critical graph dbpedia-ru:Factor-critical graph https://global.dbpedia.org/id/4jLYS |
| prov:wasDerivedFrom | wikipedia-en:Factor-critical_graph?oldid=1065655054&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Friendship_graphs.svg wiki-commons:Special:FilePath/Gyroelongated_pentagonal_pyramid.png wiki-commons:Special:FilePath/Factor_critical.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Factor-critical_graph |
| is dbo:wikiPageRedirects of | dbr:Blossom_(graph_theory) |
| is dbo:wikiPageWikiLink of | dbr:Mycielskian dbr:Perfect_matching dbr:Ear_decomposition dbr:Matching_(graph_theory) dbr:Friendship_graph dbr:Glossary_of_graph_theory dbr:Critical_graph dbr:Matching_polytope dbr:Gallai–Edmonds_decomposition dbr:Blossom_(graph_theory) dbr:Odile_Favaron |
| is dbp:properties of | dbr:Friendship_graph |
| is foaf:primaryTopic of | wikipedia-en:Factor-critical_graph |
