Consider an undirected graph <\/span> <\/span> such that the following properties hold:<\/p>\n As an example, consider the following graph:<\/p>\n <\/p>\n Here is a tree decomposition of the above graph:<\/p>\n <\/p>\n <\/p>\n In the above picture, the nodes are the blue circles, and the subgraphs induced by the bags are drawn inside the nodes. Define the width\u00a0<\/i>of a tree decomposition to be the maximal size of a bag minus one. In the example above, the width is 2, because the maximal bag size is 3. (If you don’t like doing minus one, an alternative view is that the width is the maximal intersection of two bags of adjacent nodes.) The\u00a0tree width\u00a0<\/em>of a graph is the minimal width of a tree decomposition of it.<\/p>\n <\/p>\n Sourced graphs: an algebraic view of treewidth<\/strong><\/p>\n We now present a more algebraic way of defining treewidth. Define a sourced\u00a0graph\u00a0<\/em>to be a graph with some but not necessarily all vertices being assigned natural numbers; the vertices with numbers are called the sources<\/em>. The numbers are called the source\u00a0names.\u00a0<\/em>We assume that the each source<\/em>\u00a0has one number; although the numbers used in a graph need not be a prefix of The main purpose of sourced graphs is to fuse them using a fusion operation After doing a fusion, we might want to\u00a0forget <\/em>some\u00a0<\/em>source names. For this we use an extended forgetting\u00a0<\/em>version of the fusion operation Note that the two sourced graphs above share common source\u00a0names, namely\u00a02 and 4, while the source names 1 and 3 are not common. Therefore, when fusing\u00a0them we will do two merges: one for source name 2, and one for source name 4.\u00a0Suppose that the two sourced graphs above are combined\u00a0using the operation <\/p>\n The colours blue, yellow and green are supposed to indicate which of the inputs was used to produce which vertex, and they are not part of the actual\u00a0sourced graph.<\/p>\n Algebra of sourced graphs.\u00a0<\/strong>The set of sourced graphs can be viewed as an algebra, which we call the algebra of sourced graphs.<\/em>\u00a0This algebra\u00a0has a constant for every sourced graph, and a binary operation ![\"G\"](\"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-content\/ql-cache\/quicklatex.com-ef7dc8eeb66accf1fa3b705f6382f071_l3.png\" "\\"Rendered")
. Define a\u00a0tree decomposition<\/em> of \u00a0to be a tree ![\"t\"](\"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-content\/ql-cache\/quicklatex.com-3374f32a602fe8fdc50593fbb0e5bde1_l3.png\" "\\"Rendered")
together with a labelling <\/p>\n![\"\[v \in \text{nodes of $t$} \qquad \mapsto \qquad \text{bag of $v$ $\subseteq $ vertices of $G$}\]\"](\"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-content\/ql-cache\/quicklatex.com-0846e046362137b21a77f606f69e2f9c_l3.png\" "\\"Rendered")
<\/p>\n\n
is contained in bag of \u00a0;<\/li>\n, the set of nodes in whose bags contain ![\"v\"](\"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-content\/ql-cache\/quicklatex.com-8ecbc11e5f9047eaecdbfca853b87fd1_l3.png\" "\\"Rendered")
is connected via the child relation.<\/li>\n<\/ul>\n![\"mso-courcelle-03\"](\"http:\/\/www.mimuw.edu.pl\/~bojan\/upload\/mso-courcelle-03.svg\")
<\/a><\/p>\n<\/a><\/p>\n
\n.\u00a0A sourced graph with no sources is\u00a0the same thing as a graph. \u00a0Here is a picture of a sourced graph, with the\u00a0source names used being :<\/p>\n<\/p>\n. The operation inputs two sourced graphs. On the output, it\u00a0produces the disjoint union of the two inputs, with each pair of sources that have the same name being merged\u00a0together into a single vertex (when we merged\u00a0vertices and , all edges incident with and are redirected to the new merged\u00a0vertex). The fusion operation can easily be extended to take not two arguments, but any number of arguments in . When there is one argument, nothing happens.<\/p>\n, where the index is a set source names, i.e. natural numbers. When this operation is applied, we first do the fusion as described above, and then we only keep the source names from , while sources\u00a0with names outside become non-sources. Let us illustrate the forgetting fusion operation on an example. Consider the following two\u00a0sourced graphs:<\/p>\n<\/p>\n. The result will be the following interface graph.<\/p>\n<\/a><\/p>\n for every finite set of source names. Here is an example of a term in the algebra of sourced graphs which generates a cycle of length 6:<\/p>\n