About: Lexicographic product of graphs     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:Whole100003553, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon
http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FLexicographic_product_of_graphs&invfp=IFP_OFF&sas=SAME_AS_OFF

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.

AttributesValues
rdf:type
rdfs:label
  • Lexicographic product of graphs (en)
  • Лексикографическое произведение графов (ru)
  • 图的字典积 (zh)
rdfs:comment
  • Лексикографическое произведение или суперпозиция графов — конструкция графа по данным двум.Если связи рёбер в двух графах являются отношениями порядка, то связь рёбер в их лексикографическом произведении является соответствующим лексикографическим порядком — отсюда название. Лексикографическое произведение первым изучал Феликс Хаусдорф. (ru)
  • 在图论中，图G和 H的字典积是一个图，使得 * 其顶点集是笛卡尔积 V(G) × V(H); * 其任意两个顶点 (u,v) 和 (x,y) 相邻当且仅当在 G 中 u 与 x 相邻或相同，并且在 H 中 v 与 y 相邻。 如果两个图的边表示两种偏序关系，那么它们的字典积的边就表示其对应的字典序。 Felix Hausdorff于1914年首次研究了字典积。Feigenbaum 与 Schäffer于1986年证明了，判别图是否为字典积的问题在复杂性上与判别图是否同构的问题等价。 (zh)
  • 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. (en)
foaf:depiction
  • http://commons.wikimedia.org/wiki/Special:FilePath/Graph-lexicographic-product.svg
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
thumbnail
authorlink
  • Felix Hausdorff (en)
first
  • Felix (en)
last
  • Hausdorff (en)
title
  • Graph Lexicographic Product (en)
urlname
  • GraphLexicographicProduct (en)
year
has abstract
  • 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. (en)
  • Лексикографическое произведение или суперпозиция графов — конструкция графа по данным двум.Если связи рёбер в двух графах являются отношениями порядка, то связь рёбер в их лексикографическом произведении является соответствующим лексикографическим порядком — отсюда название. Лексикографическое произведение первым изучал Феликс Хаусдорф. (ru)
  • 在图论中，图G和 H的字典积是一个图，使得 * 其顶点集是笛卡尔积 V(G) × V(H); * 其任意两个顶点 (u,v) 和 (x,y) 相邻当且仅当在 G 中 u 与 x 相邻或相同，并且在 H 中 v 与 y 相邻。 如果两个图的边表示两种偏序关系，那么它们的字典积的边就表示其对应的字典序。 Felix Hausdorff于1914年首次研究了字典积。Feigenbaum 与 Schäffer于1986年证明了，判别图是否为字典积的问题在复杂性上与判别图是否同构的问题等价。 (zh)
gold:hypernym
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is Wikipage redirect of
is Wikipage disambiguates of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 59 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software