các định nghĩa đồ thị

Đồ thị (Graph) 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ị. Để minh chứng cho các loại đồ thị, chúng ta xem xét một số ví dụ về các loại mạng máy tính
bao gồm: mỗi máy tính là một đỉnh, mỗi cạnh là những kênh điện thoại được nối giữa hai máy
tính với nhau.
Định nghĩa 1. Đơ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.

Định nghĩa 2. Đ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.

Định nghĩa 3. 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.

Định nghĩa 4. Đơ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.

Định nghĩa 5. Đ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.

ĐƯỜNG ĐI, CHU TRÌNH, ĐỒ THỊ LIÊN THÔNG
Định nghĩa 1. Đườ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

Định nghĩa 3. Đồ 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ó.