Graph factorization (original) (raw)
Ein Faktor ist in der Graphentheorie ein Teilgraph eines Graphen, bei dem gewisse Anforderungen an den Grad der Knoten sowie an den Zusammenhang des Graphen gestellt werden. Faktoren spielen eine wichtige Rolle in der Theorie des Matching-Problems und des Hamiltonkreisproblems.
| Property | Value |
|---|---|
| dbo:abstract | Ein Faktor ist in der Graphentheorie ein Teilgraph eines Graphen, bei dem gewisse Anforderungen an den Grad der Knoten sowie an den Zusammenhang des Graphen gestellt werden. Faktoren spielen eine wichtige Rolle in der Theorie des Matching-Problems und des Hamiltonkreisproblems. (de) In graph theory, a factor of a graph G is a spanning subgraph, i.e., a subgraph that has the same vertex set as G. A k-factor of a graph is a spanning k-regular subgraph, and a k-factorization partitions the edges of the graph into disjoint k-factors. A graph G is said to be k-factorable if it admits a k-factorization. In particular, a 1-factor is a perfect matching, and a 1-factorization of a k-regular graph is an edge coloring with k colors. A 2-factor is a collection of cycles that spans all vertices of the graph. (en) Фактор графа G — это остовный подграф, то есть подграф, имеющий те же вершины, что и граф G. k-фактор графа — это остовный k-регулярный подграф, а k-факторизация разбивает рёбра графа на непересекающиеся k-факторы. Говорят, что граф G k-факторизуем, если он позволяет k-разбиение. В частности, множество рёбер 1-фактора — это совершенное паросочетание, а 1-разложение k-регулярного графа — это рёберная раскраска k цветами. 2-фактор — это набор циклов, которые покрывают все вершины графа. (ru) 在圖論中，因子是某個圖G的生成子圖，並且是與G相同的頂點的子圖。通常因子名稱前面會加一個數，例如k-因子，表示每個頂點的度均為k，換句話說即該因子為k-正則生成子圖。將某個圖G的邊分解為若干個互斥的k-因子之動作稱為k-分解。類似於除法整除的概念，如果圖G可以被k-分解，則G可以稱為k-因子分解圖（類似於G可被k整除的概念），而圖與因子間關係則可以類比為數與因數。特別地，將任意圖1-分解為1-因子是一種完美匹配，因為其結果括了圖G中原來的所有頂點；此外，若將一個k-正則圖進行1-分解則與將該k-正則圖進行k種顏色的等價。2-因子則是包含圖中的所有頂點之環的集合。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Desargues_graph_3color_edge.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ https://archive.org/details/graphtheorywitha0000bond http://www.math.uiuc.edu/~west/openp/1fact.html https://web.archive.org/web/20100413104345/http:/www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html http://users.monash.edu.au/~iwanless/data/P1F/newP1F.html |
| dbo:wikiPageID | 3298854 (xsd:integer) |
| dbo:wikiPageLength | 11089 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1099535997 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Euler_tour dbr:Perfect_matching dbr:Regular_graph dbr:Regular_polygon dbr:Cycle_(graph_theory) dbc:Graph_theory_objects dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Petersen_graph dbr:Glossary_of_graph_theory dbr:Conjecture dbr:Anton_Kotzig dbr:Hall's_marriage_theorem dbr:Hamiltonian_decomposition dbr:Acta_Mathematica dbr:Julius_Petersen dbr:Edge_coloring dbr:Baranyai's_theorem dbr:Discrete_Mathematics_(journal) dbr:Graph_theory dbr:Hypergraph dbr:Bipartite_graph dbc:Factorization dbr:Springer_Science+Business_Media dbr:Chromatic_index dbr:Round-robin_tournament dbr:Oberwolfach_problem dbr:Overfull_conjecture dbr:Hamiltonian_cycle dbr:Spanning_subgraph dbr:File:Desargues_graph_3color_edge.svg dbr:File:Complete-edge-coloring.svg dbr:File:Petersen-graph-factors.svg |
| dbp:id | p/o110070 (en) |
| dbp:title | Graph Factor (en) One-factorization (en) k-Factor (en) k-Factorable Graph (en) |
| dbp:urlname | GraphFactor (en) k-Factor (en) k-FactorableGraph (en) |
| dbp:wikiPageUsesTemplate | dbt:Springer dbt:Citation dbt:Cite_web dbt:Distinguish dbt:Harvtxt dbt:MathWorld dbt:Refbegin dbt:Refend dbt:Reflist dbt:Oeis |
| dct:subject | dbc:Graph_theory_objects dbc:Factorization |
| gold:hypernym | dbr:Subgraph |
| rdf:type | owl:Thing yago:WikicatConjectures yago:Abstraction100002137 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Hypothesis105888929 yago:Idea105833840 yago:PsychologicalFeature100023100 yago:Speculation105891783 |
| rdfs:comment | Ein Faktor ist in der Graphentheorie ein Teilgraph eines Graphen, bei dem gewisse Anforderungen an den Grad der Knoten sowie an den Zusammenhang des Graphen gestellt werden. Faktoren spielen eine wichtige Rolle in der Theorie des Matching-Problems und des Hamiltonkreisproblems. (de) In graph theory, a factor of a graph G is a spanning subgraph, i.e., a subgraph that has the same vertex set as G. A k-factor of a graph is a spanning k-regular subgraph, and a k-factorization partitions the edges of the graph into disjoint k-factors. A graph G is said to be k-factorable if it admits a k-factorization. In particular, a 1-factor is a perfect matching, and a 1-factorization of a k-regular graph is an edge coloring with k colors. A 2-factor is a collection of cycles that spans all vertices of the graph. (en) Фактор графа G — это остовный подграф, то есть подграф, имеющий те же вершины, что и граф G. k-фактор графа — это остовный k-регулярный подграф, а k-факторизация разбивает рёбра графа на непересекающиеся k-факторы. Говорят, что граф G k-факторизуем, если он позволяет k-разбиение. В частности, множество рёбер 1-фактора — это совершенное паросочетание, а 1-разложение k-регулярного графа — это рёберная раскраска k цветами. 2-фактор — это набор циклов, которые покрывают все вершины графа. (ru) 在圖論中，因子是某個圖G的生成子圖，並且是與G相同的頂點的子圖。通常因子名稱前面會加一個數，例如k-因子，表示每個頂點的度均為k，換句話說即該因子為k-正則生成子圖。將某個圖G的邊分解為若干個互斥的k-因子之動作稱為k-分解。類似於除法整除的概念，如果圖G可以被k-分解，則G可以稱為k-因子分解圖（類似於G可被k整除的概念），而圖與因子間關係則可以類比為數與因數。特別地，將任意圖1-分解為1-因子是一種完美匹配，因為其結果括了圖G中原來的所有頂點；此外，若將一個k-正則圖進行1-分解則與將該k-正則圖進行k種顏色的等價。2-因子則是包含圖中的所有頂點之環的集合。 (zh) |
| rdfs:label | Faktor (Graphentheorie) (de) Graph factorization (en) Факторизация графа (ru) 因子 (圖論) (zh) Факторизація графа (uk) |
| owl:differentFrom | dbr:Factor_graph |
| owl:sameAs | freebase:Graph factorization wikidata:Graph factorization dbpedia-de:Graph factorization dbpedia-fa:Graph factorization yago-res:Graph factorization dbpedia-ru:Graph factorization dbpedia-sk:Graph factorization dbpedia-uk:Graph factorization dbpedia-zh:Graph factorization https://global.dbpedia.org/id/4kTrN |
| prov:wasDerivedFrom | wikipedia-en:Graph_factorization?oldid=1099535997&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Complete-edge-coloring.svg wiki-commons:Special:FilePath/Desargues_graph_3color_edge.svg wiki-commons:Special:FilePath/Petersen-graph-factors.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Graph_factorization |
| is dbo:wikiPageRedirects of | dbr:1-factorization dbr:1-factorization_conjecture dbr:1-factor dbr:Factor_(graph_theory) dbr:Graph_factor dbr:K-factor_(graph_theory) dbr:2-factor dbr:One-factorization dbr:1-factorability dbr:1-factorable dbr:K-Factorable_graph |
| is dbo:wikiPageWikiLink of | dbr:Anthony_Hilton dbr:Perfect_matching dbr:Cycle_decomposition_(graph_theory) dbr:Dejter_graph dbr:1-factorization dbr:1-factorization_conjecture dbr:132_(number) dbr:1-factor dbr:Glossary_of_graph_theory dbr:Snark_(graph_theory) dbr:Steiner_system dbr:Hamiltonian_decomposition dbr:Baranyai's_theorem dbr:Graph_Theory,_1736–1936 dbr:Graph_theory dbr:Factor_(graph_theory) dbr:2-factor_theorem dbr:Italo_Jose_Dejter dbr:Bipartite_realization_problem dbr:Blow-up_lemma dbr:Automorphisms_of_the_symmetric_and_alternating_groups dbr:Graph_factor dbr:K-factor_(graph_theory) dbr:Prism_graph dbr:Room_square dbr:Quartic_graph dbr:2-factor dbr:One-factorization dbr:1-factorability dbr:1-factorable dbr:K-Factorable_graph |
| is owl:differentFrom of | dbr:Factor_graph |
| is foaf:primaryTopic of | wikipedia-en:Graph_factorization |
