Đồ thị vô hướng liên thông
Trong mục này chúng ta sẽ trình bày một số thuật ngữ cơ bản của lý thuyết đồ thị. Trước tiên, ta xét các thuật ngữ mô tả các đỉnh và cạnh của đồ thị vô hướng. Định nghĩa 1.13 Hai đỉnh u và v của đồ thị vô hướng G ...
Trong mục này chúng ta sẽ trình bày một số thuật ngữ cơ bản của lý thuyết đồ thị. Trước tiên, ta xét các thuật ngữ mô tả các đỉnh và cạnh của đồ thị vô hướng.
Định nghĩa 1.13
Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu (u,v) là cạnh của đồ thị G. Nếu e = (u, v) là cạnh của đồ thị ta nói cạnh này là liên thuộc với hai đỉnh u và v, hoặc cũng nói là nối đỉnh u và đỉnh v, đồng thời các đỉnh u và v sẽ được gọi là các đỉnh đầu của cạnh (u, v).
Để có thể biết có vao nhiêu cạnh liên thuộc với một đỉnh, ta đưa vào định nghĩa sau
Định nghĩa 1.14
Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó và sẽ ký hiệu là deg(v).
Hình 1.9 Đồ thị vô hướng.
Ví dụ 1.7 Xét đồ thị cho trong hình 1.9, ta có
deg(a) = 1, deg(b) = 4, deg(c) = 4, deg(f) = 3,
deg(d) = 1, deg(e) = 3, deg(g) = 0
Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 được gọi là đỉnh treo. Trong ví dụ trên đỉnh g là đỉnh cô lập, a và d là các đỉnh treo. Bậc của đỉnh có tính chất sau:
Định lý 1.2
Giả sử G = (V, E) là đồ th ị vô hướng với m cạnh. Khi đó tổng bậc của tất cả các đỉnh bằng hai lần số cung.
Chứng minh.
Rõ ràng mỗi cạnh e = (u, v) được tính một lần trong deg(u) và một lần trong deg(v). Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh.
Ví dụ 1.8Đồ thị với n đỉnh có bậc là 6 có bao nhiêu cạnh?
Giải: Theo định lý 1.2 ta có 2m = 6n. Từ đó suy ra tổng các cạnh của đồ thị là 3n.
Hệ quả 1.3
Trong đồ thị vô hướng, số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số chẵn.
Chứng minh.
Thực vậy, gọi O và U tương ứng là tập đỉnh bậc lẻ và tập đỉnh bậc chẵn của đồ thị. Ta có
Do deg(v) là chẵn với v là đỉnh trong U nên tổng thứ nhất ở trên là số chẵn. Từ đó suy ra tổng thứ hai (chính là tổng bậc của các đỉnh bậc lẻ) cũng phải là số chẵn, do tất cả các số hạng của nó là số lẻ, nên tổng này phải gồm một số chẵn các số hạng. Vì vậy, số đỉnh bậc lẻ phải là số chẵn.
Ta xét các thuật ngữ tương tự cho đồ thị vô hướng.
