| http://dbpedia.org/ontology/abstract
|
En teoría de grafos, un homomorfismo de gr … En teoría de grafos, un homomorfismo de grafos u homomorfismo de gráficas es una función entre dos grafos que respeta la estructura de adyacencia de una en la otra. De forma más precisa: Si G, H son dos grafos, entonces un homomorfismo es una función que satisface la condición: si u, v son cualquier par de vértices de G unidos por una arista, entonces y son vértices de H que también están unidos por una arista.H que también están unidos por una arista.
, Гомоморфізм графів — це відображення між д … Гомоморфізм графів — це відображення між двома графами, що не порушує структури. Конкретніше, це відображення між наборами вершин двох графів, яке відображає суміжні вершини в суміжні. Гомоморфізми узагальнюють різні поняття розфарбовування графів і дозволяють формулювати важливі класи задач виконання обмежень, таких як деякі задачі або задачі . Факт, що гомоморфізми можна використати послідовно, приводить до багатих алгебричних структур — передпорядку на графах, дистрибутивної ґратки і категорій (одна для неорієнтованих графів і одна для орієнтованих графів). Обчислювальна складність пошуку гомоморфізму між заданими графами в загальному випадку позамежна, але відомо багато окремих випадків, коли задача здійсненна за поліноміальний час. Межі між розв'язними і нездоланними випадками є галуззю активних досліджень.и випадками є галуззю активних досліджень.
, No campo da matemática da teoria dos grafos um homomorfismo de grafos é um mapeamento entre dois grafos que respeita suas estruturas. De forma mais concreta ele mapeia vértices adjacentes a vértices adjacentes.
, Un morphisme de graphes ou homomorphisme d … Un morphisme de graphes ou homomorphisme de graphes est une application entre deux graphes (orientés ou non orientés) qui respecte la structure de ces graphes. Autrement dit l'image d'un graphe dans un graphe doit respecter les relations d'adjacence présentes dans .les relations d'adjacence présentes dans .
, 数学分支圖論中，圖同態（英語：graph homomorphism）是兩幅图之間保結 … 数学分支圖論中，圖同態（英語：graph homomorphism）是兩幅图之間保結構的映射。具體而言，該映射將某圖的各顶点映至另一圖的頂點，且若兩頂點相鄰，則其像仍然相鄰。 同態是若干種圖着色概念的推廣，適用於表達一類重要的約束滿足問題，如排程、問題。同態可以複合，為全體圖組成的類賦予豐富的代數結構：其上的预序关系、分配格結構、範疇結構（分為無向與有向圖範疇兩種）。欲尋找任意兩圖間的同態，而無額外條件，則現時所知的計算複雜度高得不切實際，但對於某些特定類別的圖，已知有多項式時間算法。此類問題易解與否，兩者的分野，是活躍的研究方向。特定類別的圖，已知有多項式時間算法。此類問題易解與否，兩者的分野，是活躍的研究方向。
, Гомоморфизм графов — это отображение между … Гомоморфизм графов — это отображение между двумя графами, не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные вершины в смежные. Гомоморфизмы обобщают различные понятия раскрасок графов и позволяет выражение важных классов задач удовлетворения ограничений, таких как некоторые задачи или задачи .Факт, что гомоморфизмы могут быть использованы последовательно, приводит к богатым алгебраическим структурам — предпорядку на графах, и категориям (одна для неориентированных графов и одна для ориентированных графов).Вычислительная сложность поиска гомоморфизма между заданными графами в общем случае запредельная, но известно много частных случаев, когда задача выполнима за полиномиальное время. Границы между решаемыми и непреодолимыми случаями находятся в области активных исследований.находятся в области активных исследований.
, In the mathematical field of graph theory, … In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices. Homomorphisms generalize various notions of graph colorings and allow the expression of an important class of constraint satisfaction problems, such as certain scheduling or frequency assignment problems.The fact that homomorphisms can be composed leads to rich algebraic structures: a preorder on graphs, a distributive lattice, and a category (one for undirected graphs and one for directed graphs).The computational complexity of finding a homomorphism between given graphs is prohibitive in general, but a lot is known about special cases that are solvable in polynomial time. Boundaries between tractable and intractable cases have been an active area of research.ases have been an active area of research.
, En grafhomomorfi är inom matematik en strukturbevarande avbildning, en homomorfi, mellan grafer. Mer specifikt avbildar den närliggande noder till närliggande noder.
|
| http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/Graph_homomorphism_into_C5.svg?width=300 +
|
| http://dbpedia.org/ontology/wikiPageExternalLink
|
http://www.maths.qmul.ac.uk/~pjc/csgnotes/hom1.pdf +
, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1a1%7Cdoi-access=free +
, http://www.mast.queensu.ca/~ctardif/articles/ghss.pdf +
, http://vrs.amsi.org.au/wp-content/uploads/sites/6/2014/09/CORRECTED-digraph-lattice-Gray-updated.pdf +
, http://vrs.amsi.org.au/projects/ +
, http://www.cs.sfu.ca/~pavol/cspCCC.pdf +
, http://www.cs.sfu.ca/~pavol/hombook.html +
, https://wwwpub.zih.tu-dresden.de/~bodirsky/Graph-Homomorphisms.pdf +
|
| http://dbpedia.org/ontology/wikiPageID
|
676328
|
| http://dbpedia.org/ontology/wikiPageLength
|
37091
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1110448117
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Kneser_graph +
, http://dbpedia.org/resource/File:Graph_homomorphism_into_C5.svg +
, http://dbpedia.org/resource/Glossary_of_graph_theory_terms +
, http://dbpedia.org/resource/Graph_rewriting +
, http://dbpedia.org/resource/Category:Graph_theory +
, http://dbpedia.org/resource/Category:Morphisms +
, http://dbpedia.org/resource/Initial_and_terminal_objects +
, http://dbpedia.org/resource/Oriented_graph +
, http://dbpedia.org/resource/Vertex_%28graph_theory%29 +
, http://dbpedia.org/resource/Graph_theory +
, http://dbpedia.org/resource/Parameterized_complexity +
, http://dbpedia.org/resource/Injective_function +
, http://dbpedia.org/resource/Neighbourhood_%28graph_theory%29 +
, http://dbpedia.org/resource/T-coloring +
, http://dbpedia.org/resource/Mathematics +
, http://dbpedia.org/resource/Computational_complexity +
, http://dbpedia.org/resource/Cycle_graph +
, http://dbpedia.org/resource/Frequency_allocation +
, http://dbpedia.org/resource/Circular_clique +
, http://dbpedia.org/resource/Frequency_assignment +
, http://dbpedia.org/resource/Covering_map +
, http://dbpedia.org/resource/Wireless_network +
, http://dbpedia.org/resource/Glossary_of_graph_theory +
, http://dbpedia.org/resource/Constraint_propagation +
, http://dbpedia.org/resource/Connectivity_%28graph_theory%29 +
, http://dbpedia.org/resource/Surjective_function +
, http://dbpedia.org/resource/Electromagnetic_interference +
, http://dbpedia.org/resource/Join_and_meet +
, http://dbpedia.org/resource/Moshe_Y._Vardi +
, http://dbpedia.org/resource/Covering_graph +
, http://dbpedia.org/resource/Bipartite_double_cover +
, http://dbpedia.org/resource/Odd_number +
, http://dbpedia.org/resource/NP-intermediate +
, http://dbpedia.org/resource/Girth_%28graph_theory%29 +
, http://dbpedia.org/resource/Loop_%28graph_theory%29 +
, http://dbpedia.org/resource/Pavol_Hell +
, http://dbpedia.org/resource/Dense_order +
, http://dbpedia.org/resource/Mycielskian +
, http://dbpedia.org/resource/L%282%2C1%29-coloring +
, http://dbpedia.org/resource/Directed_edge +
, http://dbpedia.org/resource/Martin_Grohe +
, http://dbpedia.org/resource/Antichain +
, http://dbpedia.org/resource/Treewidth +
, http://dbpedia.org/resource/Fractional_coloring +
, http://dbpedia.org/resource/Multiple_edges +
, http://dbpedia.org/resource/Decision_problem +
, http://dbpedia.org/resource/Homeomorphism_%28graph_theory%29 +
, http://dbpedia.org/resource/Local_search_%28constraint_satisfaction%29 +
, http://dbpedia.org/resource/Jaroslav_Ne%C5%A1et%C5%99il +
, http://dbpedia.org/resource/Australian_Mathematical_Sciences_Institute +
, http://dbpedia.org/resource/Primal_constraint_graph +
, http://dbpedia.org/resource/File:Graph_of_non-adjacent_weekdays.svg +
, http://dbpedia.org/resource/Join-irreducible +
, http://dbpedia.org/resource/Sidorenko%27s_conjecture +
, http://dbpedia.org/resource/File:Complete_graph_K7.svg +
, http://dbpedia.org/resource/Meet-irreducible +
, http://dbpedia.org/resource/Scheduling_%28production_processes%29 +
, http://dbpedia.org/resource/Exponential_object +
, http://dbpedia.org/resource/Poset +
, http://dbpedia.org/resource/Recursive_set +
, http://dbpedia.org/resource/La_Trobe_University +
, http://dbpedia.org/resource/Cartesian_closed_category +
, http://dbpedia.org/resource/Tensor_product_of_graphs +
, http://dbpedia.org/resource/Equivalence_class +
, http://dbpedia.org/resource/Category_%28mathematics%29 +
, http://dbpedia.org/resource/Backtracking +
, http://dbpedia.org/resource/Preorder +
, http://dbpedia.org/resource/Induced_subgraph +
, http://dbpedia.org/resource/Exponential_time_hypothesis +
, http://dbpedia.org/resource/Distributive_lattice +
, http://dbpedia.org/resource/NP-complete +
, http://dbpedia.org/resource/Graph_%28discrete_mathematics%29 +
, http://dbpedia.org/resource/Brute-force_search +
, http://dbpedia.org/resource/Chromatic_number +
, http://dbpedia.org/resource/Harmonic +
, http://dbpedia.org/resource/Complete_graph +
, http://dbpedia.org/resource/Hypercube_graph +
, http://dbpedia.org/resource/Graph_minor +
, http://dbpedia.org/resource/Median_graph +
, http://dbpedia.org/resource/Dynamic_programming +
, http://dbpedia.org/resource/Hedetniemi%27s_conjecture +
, http://dbpedia.org/resource/Constraint_satisfaction_problem +
, http://dbpedia.org/resource/Graph_isomorphism +
, http://dbpedia.org/resource/Complement_graph +
, http://dbpedia.org/resource/Homomorphism +
, http://dbpedia.org/resource/Heyting_algebra +
, http://dbpedia.org/resource/Complexity_of_constraint_satisfaction +
, http://dbpedia.org/resource/Graph_coloring +
, http://dbpedia.org/resource/Gallai%E2%80%93Hasse%E2%80%93Roy%E2%80%93Vitaver_theorem +
, http://dbpedia.org/resource/Orientation_%28graph_theory%29 +
, http://dbpedia.org/resource/File:Groetzsch-graph.svg +
, http://dbpedia.org/resource/Structure_%28mathematical_logic%29 +
, http://dbpedia.org/resource/Electronic_Journal_of_Combinatorics +
, http://dbpedia.org/resource/Bijection +
, http://dbpedia.org/resource/P_versus_NP_problem +
, http://dbpedia.org/resource/Time_complexity +
, http://dbpedia.org/resource/Inverse_function +
, http://dbpedia.org/resource/Fixed-parameter_tractable +
, http://dbpedia.org/resource/Bipartite_graph +
, http://dbpedia.org/resource/Gr%C3%B6tzsch_graph +
, http://dbpedia.org/resource/Partial_order +
, http://dbpedia.org/resource/Product_%28category_theory%29 +
, http://dbpedia.org/resource/Circular_coloring +
, http://dbpedia.org/resource/Path_graph +
, http://dbpedia.org/resource/Polynomial-time_reduction +
, http://dbpedia.org/resource/Oriented_coloring +
, http://dbpedia.org/resource/Complete_bipartite_graph +
|
| http://dbpedia.org/property/1a
|
Cameron
, Nešetřil
, Hell
|
| http://dbpedia.org/property/1loc
|
§6.1
, §6.2
, Theorem 3.30
, Proposition 2.3
|
| http://dbpedia.org/property/1p
|
1
, 192
|
| http://dbpedia.org/property/1y
|
2006
, 2004
|
| http://dbpedia.org/property/2a
|
Hahn
, Tardif
, Nešetřil
, Hell
|
| http://dbpedia.org/property/2loc
|
Proposition 1.7
, Corollary 1.32
, Theorem 2.33
, §4.4
, §4.5
|
| http://dbpedia.org/property/2p
|
127
|
| http://dbpedia.org/property/2y
|
2004
, 1997
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Citation +
, http://dbpedia.org/resource/Template:Var +
, http://dbpedia.org/resource/Template:Math +
, http://dbpedia.org/resource/Template:Shy +
, http://dbpedia.org/resource/Template:Sfn +
, http://dbpedia.org/resource/Template:Sfnm +
, http://dbpedia.org/resource/Template:Vec +
, http://dbpedia.org/resource/Template:Short_description +
, http://dbpedia.org/resource/Template:Good_article +
, http://dbpedia.org/resource/Template:Main +
, http://dbpedia.org/resource/Template:Distinguish +
, http://dbpedia.org/resource/Template:Reflist +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Graph_theory +
, http://dbpedia.org/resource/Category:Morphisms +
|
| http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Mapping +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Graph_homomorphism?oldid=1110448117&ns=0 +
|
| http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/Groetzsch-graph.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Complete_graph_K7.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Graph_homomorphism_into_C5.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Graph_of_non-adjacent_weekdays.svg +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Graph_homomorphism +
|
| owl:differentFrom |
http://dbpedia.org/resource/Graph_homeomorphism +
|
| owl:sameAs |
http://zh.dbpedia.org/resource/%E5%9C%96%E5%90%8C%E6%85%8B +
, http://dbpedia.org/resource/Graph_homomorphism +
, https://global.dbpedia.org/id/37jDi +
, http://uk.dbpedia.org/resource/%D0%93%D0%BE%D0%BC%D0%BE%D0%BC%D0%BE%D1%80%D1%84%D1%96%D0%B7%D0%BC_%D0%B3%D1%80%D0%B0%D1%84%D1%96%D0%B2 +
, http://hu.dbpedia.org/resource/Gr%C3%A1fhomomorfizmus +
, http://fa.dbpedia.org/resource/%D9%87%D9%85%D8%B1%DB%8C%D8%AE%D8%AA%DB%8C_%DA%AF%D8%B1%D8%A7%D9%81 +
, http://rdf.freebase.com/ns/m.032105 +
, http://pt.dbpedia.org/resource/Homomorfismo_de_grafos +
, http://sv.dbpedia.org/resource/Grafhomomorfi +
, http://ru.dbpedia.org/resource/%D0%93%D0%BE%D0%BC%D0%BE%D0%BC%D0%BE%D1%80%D1%84%D0%B8%D0%B7%D0%BC_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 +
, http://es.dbpedia.org/resource/Homomorfismo_de_grafos +
, http://vi.dbpedia.org/resource/Ph%C3%A9p_%C4%91%E1%BB%93ng_c%E1%BA%A5u_%C4%91%E1%BB%93_th%E1%BB%8B +
, http://fr.dbpedia.org/resource/Morphisme_de_graphes +
, http://www.wikidata.org/entity/Q3385162 +
|
| rdf:type |
http://dbpedia.org/ontology/Software +
|
| rdfs:comment |
数学分支圖論中，圖同態（英語：graph homomorphism）是兩幅图之間保結 … 数学分支圖論中，圖同態（英語：graph homomorphism）是兩幅图之間保結構的映射。具體而言，該映射將某圖的各顶点映至另一圖的頂點，且若兩頂點相鄰，則其像仍然相鄰。 同態是若干種圖着色概念的推廣，適用於表達一類重要的約束滿足問題，如排程、問題。同態可以複合，為全體圖組成的類賦予豐富的代數結構：其上的预序关系、分配格結構、範疇結構（分為無向與有向圖範疇兩種）。欲尋找任意兩圖間的同態，而無額外條件，則現時所知的計算複雜度高得不切實際，但對於某些特定類別的圖，已知有多項式時間算法。此類問題易解與否，兩者的分野，是活躍的研究方向。特定類別的圖，已知有多項式時間算法。此類問題易解與否，兩者的分野，是活躍的研究方向。
, Гомоморфизм графов — это отображение между … Гомоморфизм графов — это отображение между двумя графами, не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные вершины в смежные. Гомоморфизмы обобщают различные понятия раскрасок графов и позволяет выражение важных классов задач удовлетворения ограничений, таких как некоторые задачи или задачи .Факт, что гомоморфизмы могут быть использованы последовательно, приводит к богатым алгебраическим структурам — предпорядку на графах, и категориям (одна для неориентированных графов и одна для ориентированных графов).Вычислительная сложность поиска гомоморфизма между заданными графами в общем случае запредельная, но известно много частных случаев, когда задача выполнима за полиномиальное время. Границы между решаемыми и непреодолимемя. Границы между решаемыми и непреодолим
, In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices.
, Гомоморфізм графів — це відображення між д … Гомоморфізм графів — це відображення між двома графами, що не порушує структури. Конкретніше, це відображення між наборами вершин двох графів, яке відображає суміжні вершини в суміжні. Гомоморфізми узагальнюють різні поняття розфарбовування графів і дозволяють формулювати важливі класи задач виконання обмежень, таких як деякі задачі або задачі . Факт, що гомоморфізми можна використати послідовно, приводить до багатих алгебричних структур — передпорядку на графах, дистрибутивної ґратки і категорій (одна для неорієнтованих графів і одна для орієнтованих графів). Обчислювальна складність пошуку гомоморфізму між заданими графами в загальному випадку позамежна, але відомо багато окремих випадків, коли задача здійсненна за поліноміальний час. Межі між розв'язними і нездоланними випадками є галуозв'язними і нездоланними випадками є галу
, No campo da matemática da teoria dos grafos um homomorfismo de grafos é um mapeamento entre dois grafos que respeita suas estruturas. De forma mais concreta ele mapeia vértices adjacentes a vértices adjacentes.
, En grafhomomorfi är inom matematik en strukturbevarande avbildning, en homomorfi, mellan grafer. Mer specifikt avbildar den närliggande noder till närliggande noder.
, Un morphisme de graphes ou homomorphisme d … Un morphisme de graphes ou homomorphisme de graphes est une application entre deux graphes (orientés ou non orientés) qui respecte la structure de ces graphes. Autrement dit l'image d'un graphe dans un graphe doit respecter les relations d'adjacence présentes dans .les relations d'adjacence présentes dans .
, En teoría de grafos, un homomorfismo de gr … En teoría de grafos, un homomorfismo de grafos u homomorfismo de gráficas es una función entre dos grafos que respeta la estructura de adyacencia de una en la otra. De forma más precisa: Si G, H son dos grafos, entonces un homomorfismo es una función que satisface la condición: si u, v son cualquier par de vértices de G unidos por una arista, entonces y son vértices de H que también están unidos por una arista.H que también están unidos por una arista.
|
| rdfs:label |
圖同態
, Graph homomorphism
, Homomorfismo de grafos
, Grafhomomorfi
, Гомоморфизм графов
, Morphisme de graphes
, Гомоморфізм графів
|
