| http://dbpedia.org/ontology/abstract
|
Лексикографическое произведение или суперп … Лексикографическое произведение или суперпозиция графов — конструкция графа по данным двум.Если связи рёбер в двух графах являются отношениями порядка, то связь рёбер в их лексикографическом произведении является соответствующим лексикографическим порядком — отсюда название. Лексикографическое произведение первым изучал Феликс Хаусдорф.роизведение первым изучал Феликс Хаусдорф.
, In graph theory, the lexicographic product … In graph theory, the lexicographic product or (graph) composition G ∙ H of graphs G and H is a graph such that
* the vertex set of G ∙ H is the cartesian product V(G) × V(H); and
* any two vertices (u,v) and (x,y) are adjacent in G ∙ H if and only if either u is adjacent with x in G or u = x and v is adjacent with y in H. If the edge relations of the two graphs are order relations, then the edge relation of their lexicographic product is the corresponding lexicographic order. The lexicographic product was first studied by Felix Hausdorff. As showed, the problem of recognizing whether a graph is a lexicographic product is equivalent in complexity to the graph isomorphism problem.mplexity to the graph isomorphism problem.
, 在图论中，图G和 H的字典积是一个图，使得
* 其顶点集是笛卡尔积 V(G) × V(H);
* 其任意两个顶点 (u,v) 和 (x,y) 相邻当且仅当在 G 中 u 与 x 相邻或相同，并且在 H 中 v 与 y 相邻。 如果两个图的边表示两种偏序关系，那么它们的字典积的边就表示其对应的字典序。 Felix Hausdorff于1914年首次研究了字典积。Feigenbaum 与 Schäffer于1986年证明了，判别图是否为字典积的问题在复杂性上与判别图是否同构的问题等价。
|
| http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/Graph-lexicographic-product.svg?width=300 +
|
| http://dbpedia.org/ontology/wikiPageID
|
6026731
|
| http://dbpedia.org/ontology/wikiPageLength
|
3940
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
951239723
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Journal_of_Combinatorial_Theory +
, http://dbpedia.org/resource/Lexicographical_order +
, http://dbpedia.org/resource/Cartesian_product +
, http://dbpedia.org/resource/Category:Graph_products +
, http://dbpedia.org/resource/Complement_%28graph_theory%29 +
, http://dbpedia.org/resource/Independence_number +
, http://dbpedia.org/resource/Self-complementary_graph +
, http://dbpedia.org/resource/File:Graph-lexicographic-product.svg +
, http://dbpedia.org/resource/Distributivity +
, http://dbpedia.org/resource/Fractional_coloring +
, http://dbpedia.org/resource/Graph_isomorphism_problem +
, http://dbpedia.org/resource/Clique_number +
, http://dbpedia.org/resource/Chromatic_number +
, http://dbpedia.org/resource/Order_theory +
, http://dbpedia.org/resource/Commutativity +
, http://dbpedia.org/resource/Perfect_graph +
, http://dbpedia.org/resource/Graph_theory +
, http://dbpedia.org/resource/SIAM_Journal_on_Computing +
|
| http://dbpedia.org/property/authorlink
|
Felix Hausdorff
|
| http://dbpedia.org/property/first
|
Felix
|
| http://dbpedia.org/property/last
|
Hausdorff
|
| http://dbpedia.org/property/title
|
Graph Lexicographic Product
|
| http://dbpedia.org/property/urlname
|
GraphLexicographicProduct
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Mvar +
, http://dbpedia.org/resource/Template:Citation +
, http://dbpedia.org/resource/Template:Harvs +
, http://dbpedia.org/resource/Template:Harv +
, http://dbpedia.org/resource/Template:= +
, http://dbpedia.org/resource/Template:Harvtxt +
, http://dbpedia.org/resource/Template:Math +
, http://dbpedia.org/resource/Template:Mathworld +
|
| http://dbpedia.org/property/year
|
1914
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Graph_products +
|
| http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Graph +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Lexicographic_product_of_graphs?oldid=951239723&ns=0 +
|
| http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/Graph-lexicographic-product.svg +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Lexicographic_product_of_graphs +
|
| owl:sameAs |
http://rdf.freebase.com/ns/m.0fl6_x +
, http://ru.dbpedia.org/resource/%D0%9B%D0%B5%D0%BA%D1%81%D0%B8%D0%BA%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B8%D0%B7%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 +
, http://hu.dbpedia.org/resource/Gr%C3%A1fok_lexikografikus_szorzata +
, https://global.dbpedia.org/id/4pwMT +
, http://dbpedia.org/resource/Lexicographic_product_of_graphs +
, http://yago-knowledge.org/resource/Lexicographic_product_of_graphs +
, http://zh.dbpedia.org/resource/%E5%9B%BE%E7%9A%84%E5%AD%97%E5%85%B8%E7%A7%AF +
, http://www.wikidata.org/entity/Q6537715 +
|
| rdf:type |
http://dbpedia.org/class/yago/Whole100003553 +
, http://dbpedia.org/class/yago/Artifact100021939 +
, http://dbpedia.org/class/yago/WikicatGraphProducts +
, http://dbpedia.org/ontology/Software +
, http://dbpedia.org/class/yago/PhysicalEntity100001930 +
, http://dbpedia.org/class/yago/Commodity103076708 +
, http://dbpedia.org/class/yago/Object100002684 +
, http://dbpedia.org/class/yago/Merchandise103748886 +
|
| rdfs:comment |
Лексикографическое произведение или суперп … Лексикографическое произведение или суперпозиция графов — конструкция графа по данным двум.Если связи рёбер в двух графах являются отношениями порядка, то связь рёбер в их лексикографическом произведении является соответствующим лексикографическим порядком — отсюда название. Лексикографическое произведение первым изучал Феликс Хаусдорф.роизведение первым изучал Феликс Хаусдорф.
, 在图论中，图G和 H的字典积是一个图，使得
* 其顶点集是笛卡尔积 V(G) × V(H);
* 其任意两个顶点 (u,v) 和 (x,y) 相邻当且仅当在 G 中 u 与 x 相邻或相同，并且在 H 中 v 与 y 相邻。 如果两个图的边表示两种偏序关系，那么它们的字典积的边就表示其对应的字典序。 Felix Hausdorff于1914年首次研究了字典积。Feigenbaum 与 Schäffer于1986年证明了，判别图是否为字典积的问题在复杂性上与判别图是否同构的问题等价。
, In graph theory, the lexicographic product … In graph theory, the lexicographic product or (graph) composition G ∙ H of graphs G and H is a graph such that
* the vertex set of G ∙ H is the cartesian product V(G) × V(H); and
* any two vertices (u,v) and (x,y) are adjacent in G ∙ H if and only if either u is adjacent with x in G or u = x and v is adjacent with y in H. If the edge relations of the two graphs are order relations, then the edge relation of their lexicographic product is the corresponding lexicographic order. is the corresponding lexicographic order.
|
| rdfs:label |
Lexicographic product of graphs
, 图的字典积
, Лексикографическое произведение графов
|
