![\"hyperproduct.jpg\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_213.jpg?resize=278%2C196\")
<\/p>\n<\/p>\n
Often, we use graphs as a structured representation of some kind of information. Many interesting problems involving the things we’re representing can then by described in terms of operations over
\ngraphs. Today, I’m going to talk about some of the basic operations that we can do on graphs, and in later posts, we’ll see how those operations are used to solve graph-based problems.<\/p>\n
\n![\"graph-powers.jpg\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_214.jpg?resize=167%2C274\")
<\/p>\n
The easiest thing to describe is exponents of a graph. Given a graph G=(V,E), for The next most common operation – or in the case of graphs, family<\/em> of operations – is product. For graphs, there are a variety of different kinds of graph products: cartesian product, lexicographic (or ordered) product, tensor product, and strong product are the most common ones. All of them have the same vertex sets, but they each have different ways of defining the edges.<\/p>\n In all of the graph products, the set of vertices of two graphs G=(V,E) and H=(W,F) is The cartesian product is the simplest one. For any two vertices (v,w) and (v’,w’) in the cartesian product of G and H, then there is an edge between (v,v’) and (w,w’) if and only if v=v’and (w,w’) is an edge in H, or w=w’ and (v,v’) is an edge in G. That sounds kind of frightening, but it’s really (note: there was an error in the original version of the above paragraph, mixing the v’s and w’s.)<\/em><\/p>\n One thing that I think is rather cool about the cartesian product is that it preserves hypercubes. A hypercube is, basically, what you get if you take an N-dimensional cube, make each corner a vertex, and then put edges between two vertices in the graph if there’s a cube edge between the corners corresponding to the two corners. What it means to preserve hypercubes is: if you take the cartesian product of two hypercubes, the result is also a hypercube. The product of a square (a 2-cube) and a line (a 1-cube) is a common three-dimensional cube. The product of two squares is a tesseract – a 4-cube. There’s an illustration of the product of two squares laid out and colored as best I can to make the tesseract structure clear up in the header of this post.<\/p>\n The tensor product of two graphs has a set of edges that’s actually easier to understand in the The lexicographic product looks strange in its definition. But the idea of it is actually (Note: in the original version of the above paragraph, I wrote that lexicographic product Often, we use graphs as a structured representation of some kind of information. Many interesting problems involving the things we’re representing can then by described in terms of operations over graphs. Today, I’m going to talk about some of the basic operations that we can do on graphs, and in later posts, we’ll see how […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[25],"tags":[],"class_list":["post-476","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-7G","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/476","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=476"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/476\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=476"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=476"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=476"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nan integer n, Gn<\/sup> is a graph with the same vertices as G, and with edges between
\ntwo vertices v and w if and only if there is a path between v and w that contains fewer
\nthan n edges. For a finite graph, after a finite number of steps, increasing the exponent won’t
\nchange the graph – the graph contains edges between any nodes that will ever be connected. That
\ngraph is called the closure<\/em> of G, written G*<\/sup>. If G is an undirected,
\nconnected graph, then G*<\/sup> will be Kx<\/sup> where x is the number of vertices in G.
\nFor an example of exponents and closure, see the graph to the left, which shows a graph G, G2<\/sup>, and G3<\/sup>. For this graph, G*<\/sup> is the same as G3<\/sup>.<\/p>\n
\nV×W – that is, the set of pairs of a vertex from V and a vertex from W. So, if G is
\na graph with vertices{A,B,C,D}, and H is a graph with vertices {1,2,3}, then the set of vertices in the product of G and H
\nis {(A,1),(A,2),(A,3),(B,1),(B,2),(B,3),(C,1),(C,2),(C,3),(D,1),(D,2),(D,3),}.<\/p>\n![\"cartesian-product.jpg\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_215.jpg?resize=276%2C303\")
<\/p>\n
\npretty straightforward, as you can see by looking at an example. It’s a straightforward version of
\nthe basic idea of cartesian product in sets or topologies. The idea of it is basically
\nthat for any vertex in G, there’s a copy of H (with edges), and the copies are connected in the structure of G. For example, to the right is a simple pair of graphs – one with four vertices, and
\nthe second one with three. Beneath it is a drawing of the cartesian product of the two graphs. The cartesian graph product is commutative and associative, and it’s normally written as a box: A[]B. (Not quite the right thing, but I couldn’t find an HTML entity for a hollow square.)<\/p>\n![\"graph-tensor-product.jpg\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_216.jpg?resize=264%2C244\")
<\/p>\n
\ndefinition, but it’s a tad harder to understand what it means. The edges are a subset of the edges in
\nthe cartesian product. In the tensor product, there is an edge between (v,w) and (v’,w’) if and only
\nif (v,v’) is an edge in G, and (w,w’) is an edge in H. You can see it as a kind of a join of the edges
\nin G and H – an edge between paired vertices only exists if there is an edge between both of the
\nvertices that make up the pair in the original graph. To the left, there’s an example of the tensor
\nproduct for the same pair of graphs as the cartesian product example. The tensor product is also the product in the category of graphs – which, in some sense, makes it the most fundamental form of the product. (Just to make things confusing, the cartesian product of graphs is not<\/em> not a categorial product, but a tensor.) Tensor product is associative and commutative, and is written using the usual product notation: A×B. Tensor product doesn’t preserve hypercubes, but it does preserve bipartiteness: the tensor product of two bipartite graphs is a bipartite graph. <\/p>\n
\nrelatively simple. If you use ordered<\/em> graphs in the lexicographic product, it actually makes
\na lot of sense. Treat each graph as the definition of a partial order over its sets of vertices. Then
\nthe lexicographic product is a graph which defines a partial order of the product of the two sets
\nwhich is consistent with the orderings over the two member sets. To be precise about it, the
\nlexicographic product of two graphs has an edge between (v,w) and (v’,w’) if and only if G contains an
\nedge (v,v’), or v=w and (w,w’) is an edge in H. Lexicographic product is (obviously) not commutative
\n– the order in which graphs are combined using lexicographic product is crucial. It’s
\ngenerally written like scalar product A*B; it’s also often called graph composition<\/em>. For
\nour example graph, the lexicographic product ends up looking the same as the cartesian product.<\/p>\n
\nwas not associative. Of course, it is – if it weren’t, then the result of multiple lexicographic products
\nof ordered graphs couldn’t possibly be consistent with the orderings of the element graphs. I don’t know what I was thinking when I wrote that; it’s a dumb error.)<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"