Giáo trình Đồ thị và các thuật toán - Chương 2: Các số cơ bản của đồ thị

Hệ quả 2.1.2 P(G) > 0 và v(G) >0. Chứng minh. Thật vậy, xuất phát từ đồ thị thành lập bằng các đỉnh của đa đồ thị vô hướng G, đỉnh nọ cô lập với đỉnh kia, ta xây dựng G dần dần từng cạnh một; khởi đầu tạ có p = 0,1 = 0; mỗi khi thêm một cạnh, thì hoặc p tăng và lúc đó e không đổi, hoặc v tăng và lúc đó , không đổi. Như vậy, trong quá trình xây dựng đô thị G, các số 2 và t chỉ có thể tăng. Để có thể vận dụng những kết quả phong phú của đại số vector trong việc nghiên cứu, người ta thường đặt tương ứng mỗi chu trình trong G với một vector theo cách sau đây: Mỗi cạnh của đa đồ thị G đều được định hướng một cách tùy ý; nếu chu trình 4 đi qua cạnh ek, Tk lần thuận hướng và đi lần ngược hướng thì ta đặt Ck := Tk - Sk (nếu ek là một khuyên thì ta luôn qui ước S = 0). Vector m chiều (C1,C2, ., Cm) gọi là vector chu trình tương ứng với 1 và ký hiệu là ả (hay là 1 nếu không thể gây ra nhầm lẫn). Các chu trình 1, 4, 4”,. gọi là độc lập nếu các vector chu trình tương ứng độc lập tuyến tính. Chú ý rằng, định nghĩa này không phụ thuộc vào hướng gán cho các cạnh.