Đồ thị có hướng liên thông

Định nghĩa 1.15

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 1.16

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 1.10 Đồ thị có hướng.

Ví dụ 1.9 Xét đồ thị cho trong hình 1.10. 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ý 1.4.

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

2m =

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.