| Bàn về graph
Vấn đề graph là vấn đề rất thú vị trong toán học. Tuy nhiên vẫn còn nhiều khái niệm và tính chất mà tôi cũng như các bạn chưa hiểu kĩ. Chính vì thế mình lập ra topic này để trao đổi về Graph và cũng trao đổi về các bài toán quốc gia, khu vực, quốc tế có sử dụng Graph, chuẩn bị cho kì VMO sắp tới
Mình xin mở đầu bằng một tính chất của đồ thi lưỡng phân do mình mới nghĩ ra, mong các bạn kiểm tra xem có chính xác không nhé:
Trong đồ thị lưỡng phân G, phân hoạch thành hai tập hợp A và B sao cho các đỉnh trong cả A và B đều không có cạnh chung. Nếu tất cả các đỉnh trong G đều có cùng bậc thì tổng số đỉnh trong A bằng tổng số đỉnh trong B. Ngoài ra số đỉnh của A bằng số đỉnh của B và bằng tổng số cạnh chia số bậc mỗi đỉnh.
Chứng minh, gọi m,n lần lượt là tổng số đỉnh ở hai tập A và B, k là bậc mỗi đỉnh. Số cạnh xuất phát từ tập A là km, từ tập B là kn. Do đây cũng chính là số cạnh của G nên km=kn suy ra m=n=|E|/k
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] |