The Matching And Partition Of Graph

Matching theory is the core of graph theory，with some important applications incombinatorial optimization and theoretical chemistry. Therefore， it has beenattentioned by many scholars. And many celebrated results have been established,suchas Hall’s theorem and Tutte’s theorem,characterizing bipartite graphs and generalgraphs with matchings. Since the extension of the field in applications and closeconnection with other subject, a series of typical topics arise. The partition of graph isa significant branch in the graph theory,vertexes coloring and edges coloring areregard as a partition of graph.Since the models of partition originates from reality, so ithas a wide application background,especially in memory allocation for computernetwork and VLSI design.The present thesis mainly purpose is to combine partition and matching.Considering a two partitions of graph and the condition of bipartite subgraph hasimmersed matching.This thesis is organized as follows:In the first chapter, the development status of matching and partitions are brieflyintroduced and some basic definitions are given.In the following chapter, according to the Hall theorem, a sufficient conditionwith degree of vertex is presented for immersed-matching of bipartite graph, and thematchings of bipartite graph and weighed bipartite graph are converted to themaximum flow for network and the maximum flow with minimum cost for network.In the third chapter, a bipartite graph meeting infiltrating matching is given by2-partitions and the condition and partition process of graph are obtained，verifiedexamples are proposed.In the fourth chapter, applications of partition and matcing to timetable problemare discussed,and a new idea to solve timetable problem is given.In the last chapter, conclusions and directions for future research are provided.