Cac Thuat Ngu Co Ban

2. CÁC THUẬT NGỮ CƠ BẢN

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.

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 2.

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. Đồ thị v� hướng

Thí dụ 1. Xét đồ thị cho trong hình 1, 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. 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.

Thí dụ 2. Đồ thị với n đỉnh có bậc là 6 có bao nhiêu cạnh?

Giải: Theo định lý 1 ta có 2m = 6n. Từ đó suy ra tổng các cạnh của đồ thị là 3n.

Hệ quả. 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ó

2m = å deg(v) + å deg(v) vÎ U vÎ O

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.

Định nghĩa 3.

Nếu e = (u, v) là cung của đồ thị có hướng G thì ta nói hai đỉnh u và v là kề nhau, và nói cung (u, v) nối đỉnh u với đỉnh v hoặc cũng nói cung này là đi ra khỏi đỉnh u và vào đỉnh v. Đỉnh u(v) sẽ được gị là đỉnh đầu (cuối) của cung (u,v).

Tương tự như khái niệm bậc, đối với đồ thị có hướng ta có khái niệm bán bậc ra và bán bậc vào của một đỉnh.

Định nghĩa 4.

Ta gọi bán bậc ra (bán bậc vào) của đỉnh v trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu là deg+(v) (deg-(v))

Hình 2. Đồ thị có hướng

Thí dụ 3. Xét đồ thị cho trong hình 2. Ta có

deg-(a)=1, deg-(b)=2, deg-(c)=2, deg-(d)=2, deg-(e) = 2.

deg+(a)=3, deg+(b)=1, deg+(c)=1, deg+(d)=2, deg+(e)=2.

Do mỗi cung (u, v) sẽ được tính một lần trong bán bậc vào của đỉnh v và một lần trong bán bậc ra của đỉnh u nên ta có:

Định lý 2. Giả sử G = (V, E) là đồ thị có hướng. Khi đó

2m = å deg+(v) + å deg-(v)

vÎ V vÎ V

Rất nhiều tính chất của đồ thị có hướng không phụ thuộc vào hướng trên các cung của nó. Vì vậy, trong nhiều trường hợp sẽ thuận tiện hơn nếu ta bỏ qua hướng trên các cung của đồ thị. Đồ thị vô hướng thu được bằng cách bỏ qua hướng trên các cung được gọi là đồ thị vô hướng tương ứng với đồ thị có hướng đã cho.