Graph Products and Configuration Processing
Graph products are defined and developed in the past 50 years (see, e.g. Berge [1], Sabidussi [2], Harary and Wilcox [3]). An excellent book covering the mathematics of graph products is that of Imrich and Klavzar [4]. In this chapter, the necessary defin
- PDF / 3,353,359 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 11 Downloads / 226 Views
Graph Products and Configuration Processing
3.1
Introduction
Graph products are defined and developed in the past 50 years (see, e.g. Berge [1], Sabidussi [2], Harary and Wilcox [3]). An excellent book covering the mathematics of graph products is that of Imrich and Klavzar [4]. In this chapter, the necessary definitions from graph products are presented and examples are included to illustrate the definitions pictorially. The number of graph products in literature is far more than four; however, products which have extensively been studied in mathematics are as follows: Cartesian graph product Strong Cartesian graph product Direct graph product Lexicographic graph product For configuration processing in structural engineering, additional new products were needed. Four such products were named and Type I, Type II, Type III and Type IV products are defined by Kaveh and Koohestani [5]. The latter types of products were obtained for subgraphs with directed members and containing loops. The corresponding product graphs have configurations most suitable for representing space structures and finite element models. Though there is no restriction in the number of subgraphs for the graph products, however, in structural mechanics the product of two subgraphs is sufficient for studying of the practical models. Again though the subgraphs can be general ones, however paths and cycles are sufficient to form most of the models encountered in structural engineering. Finally weighted graph are introduced by assigning weights to the nodes and members of the subgraphs, leading to triangular and circular products [6, 7, 8].
A. Kaveh, Optimal Analysis of Structures by Concepts of Symmetry and Regularity, DOI 10.1007/978-3-7091-1565-7_3, © Springer-Verlag Wien 2013
37
38
3.2
3 Graph Products and Configuration Processing
Definitions of Different Graph Products
Many structures have regular patterns and can be viewed as the Cartesian product, strong Cartesian product or direct product of a number of simple graphs. These subgraphs, used in the formation of a model, are called the generators of that model. In order to show different graph products with no direction (undirected graphs), the symbol (X) will be used. The indices C, SC, D and LEX will be employed to show Cartesian, strong Cartesian, direct and lexicographic, respectively. As an example, C5 (X)SC P7 shows the strong Cartesian product of the cycle C5 by the path P7.
3.2.1
Boolean Operation on Graphs
In order to explain the products of graphs, let us consider a graph S as a subset of all unordered pairs of its nodes. The node set and member set of S are denoted by N(S) and M(S), respectively. The nodes of S are labelled as s1, s2,. . .,sm,. . ., sn, and the resulting graph is a labelled graph. Two distinct adjacent nodes, sm and sn, form a member, denoted by smsn2M(S). A Boolean operation on an ordered pair of disjoint labelled graphs K and H results in a labelled graph S, which has N(K) N(H) as its nodes. The set M(S) of members of S is expressed, in terms of the m
Data Loading...
