Lý thuyết đồ thị - Đường đi - Chu trình - Đồ thị liên thông

Đồ thị: là một cấu trúc dữ liệu rời rạc bao gồm các đỉnh và các cạnh nối các cặp đỉnh này. Chúng ta phân biệt đồ thị thông qua kiểu và số lượng cạnh nối giữa các cặp đỉnh của đồ thị.

Dưới đây là một ví dụ về mạng máy tính bao gồm: mỗi máy tính là một đỉnh, mỗi kênh điện thoại kết nối là cạnh của đồ thị

Trong mạng máy tính trên, mỗi máy tính là một đỉnh của đồ thị, các kênh điện thoại là cạnh của đồ thị, không có hai cặp cạnh nào nối cùng một cặp đỉnh. Ta gọi đây là đơn đồ thị vô hướng.

Đơn đồ thị vô hướng: Đơn đồ thị vô hướng G = <V,E> bao gồm V là tập các đỉnh, E là tập các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh.

Trong trường hợp giữa máy tính nào đó thường xuyên phải truyền tải thông tin nên người ta xây dựng thêm một kênh điện thoại nữa để tăng khả năng truyền tải thông tin, khi đó hai máy tính sẽ có nhiều hơn một kênh điện thoại kết nối. Ta gọi đây là đa đồ thị vô hướng.

Đa đồ thị vô hướng: G = <V, E> bao gồm V là tập các đỉnh, E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là tập các cạnh. e1, e2 được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh.

Giả đồ thị vô hướng: G = <V, E> bao gồm V là tập đỉnh, E là họ các cặp không có thứ tự gồm hai phần tử (hai phần tử không nhất thiết phải khác nhau) trong V được gọi là các cạnh. Cạnh e được gọi là khuyên nếu có dạng e =(u, u), trong đó u là đỉnh nào đó thuộc V.

Trong nhiều mạng, các kênh kết nối giữa hai máy tính chỉ có thể truyền tải thông tin theo một chiều.Chẳng hạn máy tính đặt tại Hà Nội có thể truy cập dữ liệu của máy tính đặt tại Hải Phòng, nhưng máy tính ở Hải Phòng không thể truy cập dữ liệu của máy tính ở Hà Nội. Để mô tả mạng máy tính này chúng ta dùng khái niệm đồ thị có hướng.

Đơn đồ thị có hướng G = <V, E> bao gồm V là tập các đỉnh, E là tập các cặp có thứ tự gồm hai phần tử của V gọi là các cung.

Trong trường hợp có nhiều hơn một kênh có hướng kết nối giữa hai đỉnh của đồ thị, để mô tả mạng máy tính này ta dùng khái niệm đa đồ thị có hướng.

Mạng máy tính đa kênh một chiều

Đa đồ thị có hướng G = <V, E> bao gồm V là tập đỉnh, E là cặp có thứ tự gồm hai phần tử của V được gọi là các cung. Hai cung e1, e2 tương ứng với cùng một cặp đỉnh được gọi là cung lặp.

*Hai đỉnh u và v của đồ thị vô hướng G =<V, E> được gọi là kề nhau nếu (u,v) là cạnh thuộc đồ thị G. Nếu e =(u, v) là cạnh của đồ thị G thì ta nói cạnh này liên thuộc với hai đỉnh u và v, hoặc ta nói cạnh e nối đỉnh u với đỉnh v, đồng thời các đỉnh u và v sẽ được gọi là đỉnh đầu của cạnh (u,v).

*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à ký hiệu là deg(v).

deg(a) = 2, deg(b) =deg(c) = deg(f) = 4, deg(e) = 3, deg(d) = 1, deg(g)=0.

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. Đỉnh u sẽ được gọi là đỉnh đầu v là đỉnh cuối của cung (u,v).

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) và deg-(v).

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.

Đường đi: Đường đi độ dài n từ đỉnh u đến đỉnh v trên đồ thị vô hướng G=<V,E> là dãy: x0, x1,..., xn-1, xn trong đó n là số nguyên dương, x0=u, xn=v, (xi, xi+1)∈E, i =0, 1, 2,..., n-1.

Đường đi như trên còn có thể biểu diễn thành dãy các cạnh:

(x0, x1), (x1,x2),..., (xn-1, xn).

Đỉnh u là đỉnh đầu, đỉnh v là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (u=v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào lặp lại.

Đồ thị vô hướng được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.