Graphs with primary given d-convex sets
|
StatusThe thesis was presented on the 23 December, 2008Approved by NCAA on the 26 February, 2009 Abstract – 0.26 Mb / in romanianThesisCZU 519.17
|
Keywords
involving graph, undirected d-segment, directed d-segment, d-convex simple undirected graph(undirected geodesic graph), d-convex simple directed graph(directed geodesic graph), d-convex quasi-simple undirected graph, d-convex hull, d-convex set, anticopy vertex, copy vertex.Summary
The PhD thesis is dedicated of study of d-convexity on discrete structures through undirected and directed graphs.
There is solved the problem of characterisation of the set of d-convex simple and undirected graphs, that begins in 60-70 years of the last century. These graphs are described by using an iterative method. There are introduced a sequence of algebraic operations on the set of d-convex simple undirected graphs, that allows so to extend some known classes of graphs, also finding of some primary graphs, from which, by using these operation, could be formed the new classes of d-convex simple graphs. By this way it is determined the structure of undirected d-convex simple graphs, that is important for substantiation of convexity theory on discrete structures and for applications. It is proved the theorem of existence of bipartite d-convex simple graphs with fixed number of vertexes and edges. It is shown that the metric problems, in d-convex simple graph of type L(G, G0) are reducible to the same problems in graph G. It is determined the dimension of involving in Euclidian spaces of planar d-convex simple graphs and it is described algorithm for involving of these graphs in these spaces.
Like in case of the d-convex simple graphs, the d-convex quasi-simple graphs are described by using an iterative method. There are defined all operations that where defined for undirected d- convex simple graphs. By using them, there are studied the set of d-convex quasi-simple graphs by splitting in some special classes and are found generators for some of them. There is determined the dimension of involving in Euclidian spaces of d-convex quasi-simple planar graphs and described algorithm for involving of these graphs in these spaces.
By using the notion of distance, defined in an usual way on the set of the directed graphs, which is a semi-metric of these set of graphs, there is defined the notion of d-convex set in directed graphs.
This notion is in concordance with the axiomatic theory of convexity. There are defined the directed d-convex simple graphs, as graphs with a minimal number of the d-convex sets. The d-convex simple directed graphs are described by using an iterative method. The operations, which were defined for d-convex simple and d-convex quasi-simple undirected graphs, in addition with the operation of transposition and the L-operation, are defined on the set of directed d-convex simple graphs. It is proved that these operations are algebraic on the set of directed d-convex simple graphs, too. All this are necessary so for emphasize the structure of these graphs and the way of them constructions, also for to show that for each undirected d-convex simple graph, with known structure, there is at least one directed d-convex simple graphs, that correspond to the first, and correspondence is searched in the set of directions(orientations) of the initial undirected graph. So, it could be assert that the set of directed d-convex simple graphs contains, in this mean, the set of known undirected d-convex simple set.
Oficial Reviewers
- Dumitru Lozovanu
doctor habilitat, professor, Moldova State University - Dumitru Zambiţchi
doctor, associate professor (docent)
Theses
