Some Applications Of Nonstandard Analysis In Graph Theory

In the last half century, the study of finite graphs has attracted much attention. The research achievements are emerging in large numbers. Recently, many scholars have begun to pay attention to infinite graphs. One of the reasons is that they can be widely applied into other domains of applied mathematics. Specifically, with the integration and expansion of research fields, many scholars have begun to investigate infinite graphs by nonstandard analysis. In this thesis, we will introduce some concepts of *-finite graph by using the method of nonstandard analysis. The introduction of *-finite graph provides a new approach for researching infinite graph. Then, the galaxies of some nonstandard graphs are investigated. Finally, a nonstandard fuzzy graph is constructed and the nonstandard hull of a fuzzy graph is defined and discussed. The outline of this thesis is as follows:Section 1 presents the start, development and current research status of nonstan-dard analysis. Section 2 first gives some fundamental theories of nonstandard analysis, and then discusses several different kinds of nonstandard models, whose properties are also obtained.Section 3 gives the definition of nonstandard graph and characterizes some funda-mental concepts in graph theory by nonstandard analysis. Secondly, we define *-finite graph, for which necessary and sufficient conditions are established. Finally, using the transfer principle, we extend the theory of finite graph to *-finite graph. By virtue of this theory, we embed given infinite graph into some*-finite graph, and thus obtain the related results of infinite graph. Section 4 introduces the galaxies of nonstandard graphs and discusses the galaxies of some nonstandard graphs.In Section 5, based on general procedure for the construction of nonstandard graphs, we first construct a nonstandard fuzzy graph. Subsequently, we define the nonstandard hull of a fuzzy graph, and discuss its properties.