|
GRAPHS AND NETWORKS:
TRANSFINITE AND NONSTANDARD |
| PREFACE ``Scientia Gratia Scientiae'' It is now thirteen years since the first book that discusses transfinite graphs and electrical networks appeared, namely, ``Infinite Electrical Networks''. This was followed by two more books, ``Transfiniteness - for Graphs, Electrical Networks, and Random Walks'' and ``Pristine Transfinite Graphs and Permissive Electrical Networks,'' which compiled results from an ongoing research effort on that subject. Why then is a fourth book, this one, being offered? Simply because still more has been achieved beyond that appearing in those prior books. An exposition of these more recent results is the purpose of this book. The idea of transfiniteness for graphs and networks appeared as virgin research territory about seventeen years ago. Notwithstanding the progress that has since been achieved, much more remains to be done---or so it appears. Many conclusions concerning conventionally infinite graphs and networks can be reformulated as open problems for transfinite graphs and networks. Furthermore, questions peculiar to transfinite concepts for graphs and networks can be suggested. Indeed, these two considerations have inspired the new results displayed herein. There are presently four nonequivalent ways of introducing transfiniteness for graphs and networks. The original method is discussed in the book ``Infinite Electrical Networks.'' It views the extremities of conventionally infinite graphs as equivalence classes, called ``tips,'' of one-way infinite paths that are pairwise viewed as ``equivalent'' if they are pairwise eventually identical; connections between those tips are implemented by ``1-nodes,'' these being transfinite generalizations of conventional nodes. Such ideas can be extended to higher ranks of transfiniteness and are examined at length in the book, ``Transfiniteness - for Graphs, Electrical Networks, and Random Walks.'' A concise exposition of this approach is presented herein in Chapter 2. It turns out that transfinite connectedness is not in general a transitive binary relation between nodes. Specifically, one node may be connected to another node through a transfinite path, and the second node may be connected to a third node through another transfinite path, but there may be no transfinite path connecting the first and third nodes. This pathology can be avoided by imposing some additional restrictions on the transfinite graph. On the other hand, this difficulty disappears if the extremities (now called ``walk-tips'' or simply ``wtips'') of a graph are represented by equivalence classes of one-way infinite walks, rather than paths, with the walk-based tips being used to construct walk-based transfinite nodes. This radically expands the realm of transfinite graphs but also introduces more complicated, indeed, strange structures as walk-based transfinite graphs. The restrictions necessitated by the nontransitivity of path-connectedness are no longer needed for walk-connectedness. Chapter 5 herein presents this walk-based approach to transfinite graphs. The path-based and walk-based transfinite graphs are strictly graph-theoretic constructs. Nonetheless, by assigning electrical parameters to the branches, transfinite networks and their electrical behavior can be explored. For instance, a different approach, due to B.D. Calvert, becomes feasible when the branches are assigned positive resistances and yields another theory for transfinite electrical networks. The sums of branch resistances in paths provide path lengths, which lead to a metric for the set of nodes of a conventionally infinite, locally finite graph. That metric space is discrete. However, its completion may have limit points, and these can be interpreted as the infinite extremities of the network. Connections between those limit points then yield a transfinite network. This leads to a substantial theory for transfinite electrical networks. Moreover, it can be extended to higher ranks of transfiniteness wherein each rank has its own metric, lower-ranked metrics being stronger than higher-ranked metrics. This version of transfinite networks is examined at some length in the book, ``Pristine Transfinite Graphs and Permissive Electrical Networks,'' but it is not discussed herein. We mention it now since it is one of the four extant methods for constructing transfinite networks. The fourth and radically different approach to transfinite graphs is provided by nonstandard analysis. The nodes of a conventionally infinite graph along with the real numbers are taken as the individuals for a superstructure of sets, from which ultrapower constructions yield ``nonstandard nodes,'' ``nonstandard branches,'' and thereby ``nonstandard graphs.'' This is explored in Chapter 8, wherein ``nonstandard transfinite graphs and networks'' are also proposed. Standard theorems concerning the existence and uniqueness of current-voltage regimes in transfinite electrical networks can be lifted into a nonstandard setting with now hyperreal currents and voltages. Actually, hyperreal currents and voltages can be introduced into transfinite networks without enlarging those networks in a nonstandard way; this is the subject of Chapter 6. The idea is to view the transfinite network as the end result of an expanding sequence of finite networks that fill out the transfinite network in such a way that the connections provided by the transfinite nodes in the original network are maintained throughout the expansion procedure. This yields a sequence of currents in each branch, which can be identified as a hyperreal current for that branch, and similarly for the branch and node voltages. Thus, the transfinite network obtains a hyperreal current-voltage regime, which satisfies Kirchhoff's laws and Ohm's law, again in a particular nonstandard way. Here, however, the transfinite network will have many different hyperreal current-voltage regimes due to the many different ways of filling out the network with sequences of finite networks. Another advantage is that transfinite networks having inductors and capacitors in addition to resistors can now be admitted. (All the prior approaches to transfinite networks are restricted to purely resistive networks.) Thus, we can now examine hyperreal-valued transients in hyperreal time, as is done in Chapter 7. As a particular result of this sort, hyperreal transients on artificial and distributed, transfinite, transmission lines and cables are established. Let us also mention that a fifth method of defining transfinite graphs can be devised by starting with the ``ends'' of conventionally infinite graphs, as defined by Halin and others. However, the restriction of the infinite extremities of conventional graphs to their ends turns out to be too crude for many purposes. For example, a one-way infinite ladder has only one end, but connections to different extremities represented by the tips within that single end are needed for electrical analysis. This issue is discussed in Sec. 2.9. As for the other chapters of this book, some symbols and notations are specified and transfinite ranks are explicated in Chapter 1. Chapter 2 is a concise presentation of the earliest construction of transfinite graphs, a topic that is explored at some length in the book, ``Transfiniteness - for Graphs, Electrical Networks, and Random Walks.'' Chapter 2 provides enough information to make this book understandable independently of that prior book. In Chapter 3, some issues regarding transfinite connectedness are examined, and transfinite graphs are related to hypergraphs in a certain way. Furthermore, distances between nodes have played an important role in graph theory. Those distances are usually natural numbers. Chapter 4 extends that subject to transfinite graphs by allowing those distances to be transfinite ordinals as well. A variety of standard results are extended transfinitely in this way. This then is the scope of our book. But perhaps a few words about some general properties and peculiarities of transfinite graphs and networks might be worthwhile: Their definitions can be quite complicated. For example, a path in a conventional graph can be defined in a sentence or two, whereas the definition of a transfinite path of natural-number rank requires half a page along with another page or so of some preliminary specifications of terms used in that definition. Moreover, since paths are defined recursively along increasing transfinite ranks, with the arrow-rank paths having still another distinctive definition, the whole structure is rather cumbersome. To be sure, a concise characterization of transfinite paths is given in Sec. 2.7, but it requires that the lengthy definitions of transfinite paths be established first. This complexity is typical in all of the four different kinds of transfinite graphs and networks. Would that there were a more concise definition of transfinite paths. Perhaps there is, but it is yet to be devised. One last comment: Transfinite numbers were introduced by Cantor into mathematics over 100 years ago, and this led to a major development in the set-theoretic foundations of mathematics. This has expanded the scope of a variety of subjects in twentieth-century mathematics. In contrast, graph theory has remained on ``this side of infinity,'' notwithstanding the substantial body of results concerning conventionally infinite graphs. Undoubtedly, the advent of transfinite graphs will not by any means have the same impact as have transfinite numbers. The subject is for the most part isolated from other areas of mathematics---in contrast to conventional graph theory, but perhaps this may change. It would change if practical applications to engineering and science were to be found, but nothing of this nature exists presently. All that can be claimed is that transfinite graphs and networks comprise a new area of pure mathematics, hence the motto at the top of this Preface. Let us simply note that advancements in theory do at times reappear, perhaps unexpectedly, in real-world situations, and let us hope that such will happen for transfinite graphs. A.H. Zemanian Stony Brook, New York |
