Connectivity of Graphs Bipartite graphs and trees Trong các vấn đề như vấn đề đường đi ngắn nhất, chúng tôi tìm giải pháp tối thiểu đáp ứng các yêu cầu đã đưa ra. Các giải pháp trong những trường hợp này thường subgraphs mà không có chu kỳ. Đồ thị kết nối như vậy sẽ được gọi là cây, và chúng được sử dụng, ví dụ như, trong các thuật toán tìm kiếm cơ sở dữ liệu. Đ | 2 Connectivity of Graphs Bipartite graphs and trees In problems such as the shortest path problem we look for minimum solutions that satisfy the given requirements. The solutions in these cases are usually subgraphs without cycles. Such connected graphs will be called trees and they are used . in search algorithms for databases. For concrete applications in this respect see . Cormen . Leiserson and . Rivest Introduction to Algorithms MIT Press 1993. Certain structures with operations are representable as trees. These trees are sometimes called construction trees decomposition trees factorization trees or grammatical trees. Grammatical trees occur especially in linguistics where syntactic structures of sentences are analyzed. On the right there is a tree of operations for the arithmetic formula X- y z y. Bipartite graphs Definition. a graph G is called bipartite if To has a partition to two subsets A and Y such that each edge uv E Eg connects a vertex oQ and a vertex off. In this case A y is a bipartition of G and G is A y -bipartite. A bipartite graph G as in the above is a complete m fc - bipartite graph if A m y k and uu E Eg for all Q. ữ u E X and V E Y. All complete m fc -bipartite graphs are isomorphic. Let Kmỳ denote such a graph. A subset X c Vg is stable if G A is a discrete graph. . . . The following result is clear from the definitions. Theorem . A graph G is bipartite if and only ifVũ has a partition to two stable subsets. Example . The fc-cube of Example is bipartite for all A Indeed consider A I u has an even number oH and B I u has an odd number oH . Clearly these sets partitions and they are stable in G . Bipartite graphs and trees 17 Theorem . A graph G is bipartite if and only if it has no odd cycles. Proof. LetG be X Y -bipartite. For a cycle c fl . Vk 1 fl of length fc V1 E X implies V2 E Y V3 E X . V2i E Y V2i E X. Consequently k 1 2m 1 is oddan C1Ịseve . . Suppose that all cycles in G are even. First we observe
