Đỉnh là đối tượng, cạnh là quan hệ
Đồ thị $G=(V,E)$ gồm tập hữu hạn đỉnh V và tập cạnh E nối các đỉnh. Có thể dùng đỉnh cho các địa điểm, cạnh cho các tuyến nối trực tiếp. Đổi vị trí vẽ các đỉnh không làm đổi đồ thị nếu giữ nguyên những cặp đỉnh được nối.
Đồ thị vô hướng có cạnh đi được theo hai chiều. Đồ thị có hướng có cạnh với chiều xác định: u→v không tự cho phép v→u. Trong chuyên đề, xét **đơn đồ thị**, không có khuyên nối một đỉnh với chính nó và không có các cạnh song song cùng nối một cặp theo cùng hướng.
Sơ đồ mẫu có V={0,1,2,3,4,5,6}, bảy cạnh vô hướng và đỉnh 6 biệt lập. Đây là dữ liệu giả định, dùng xuyên suốt để đối chiếu các cách biểu diễn và duyệt.
Đỉnh kề và bậc
Hai đỉnh kề nhau khi có cạnh nối trực tiếp. Với đơn đồ thị vô hướng, bậc của một đỉnh là số đỉnh kề với nó. Trong mẫu, Adj(1)={0,3,4} nên deg(1)=3; đỉnh 6 có bậc 0. Tổng bậc bằng hai lần số cạnh vì mỗi cạnh có hai đầu: 2+3+2+2+3+2+0=14, suy ra 7 cạnh.
Với đồ thị có hướng, **bậc ra** đếm các cạnh đi ra, **bậc vào** đếm các cạnh đi tới. Ví dụ chỉ có cạnh 0→1 thì bậc ra của 0 là 1, bậc vào của 0 là 0. Không gọi 0 là đỉnh biệt lập chỉ vì bậc vào bằng 0.
Đường đi, chu trình và liên thông
Đường đi nối s đến t bằng các cạnh liên tiếp, đúng chiều nếu có hướng. Trong phạm vi bài, đường đi không lặp đỉnh; chu trình dùng các cạnh khác nhau, quay về đỉnh đầu, các đỉnh còn lại không lặp. Mẫu có đường 0→1→3→5 và chu trình 0→1→4→2→0. Mũi tên ở cách viết này chỉ chiều đang đi trên các cạnh vô hướng.
Đồ thị vô hướng liên thông khi giữa mọi cặp đỉnh đều có đường đi. Mẫu không liên thông vì 6 không nối với đỉnh khác; các thành phần liên thông là {0,1,2,3,4,5} và {6}. Một đỉnh đứng riêng cũng tạo một thành phần. Một cây là đồ thị vô hướng liên thông không có chu trình.
Đơn đồ thị vô hướng n đỉnh có nhiều nhất n(n−1)/2 cạnh: mỗi cặp đỉnh khác nhau được nối nhiều nhất một lần. Khi đạt số này, gọi là đồ thị đầy đủ; không đồng nhất “đầy đủ” với chỉ “liên thông”.
Bài luyện
Trong mẫu, đỉnh 1 kề với 0,3,4. Bậc của 1 bằng bao nhiêu?
Có ba đỉnh kề, không phải hai.
Đúng. Mỗi đỉnh kề tạo một cạnh ở đỉnh 1.
7 là số cạnh toàn đồ thị.
Không đếm mọi đỉnh khác nếu không có cạnh trực tiếp.
Lời giải
Đơn đồ thị vô hướng không có cạnh song song hoặc khuyên. Đỉnh 1 có ba cạnh nối tới 0,3,4 nên bậc của nó là 3.
Bài luyện
Chỉ có cạnh có hướng 0→1. Điều nào đúng?
Không có cạnh ngược trong dữ kiện.
0 vẫn có cạnh đi ra.
Đúng. Phải phân biệt chiều vào và chiều ra.
Cạnh đi vào 1, không đi ra từ 1.
Lời giải
Cạnh xuất phát ở 0 và kết thúc ở 1 nên đóng góp một vào bậc ra của 0, một vào bậc vào của 1. Không có cạnh đi vào 0, do đó bậc vào của 0 là 0.
Bài luyện
Vì sao đồ thị mẫu không liên thông?
Có chu trình vẫn có thể liên thông.
Nhiều đường đi không làm mất tính liên thông.
Bố trí hình vẽ không quyết định liên thông.
Đúng. Không phải mọi cặp đỉnh đều nối được bằng đường đi.
Lời giải
Đỉnh 6 không có cạnh nào nên không thể đi từ 6 đến 0,…,5. Điều kiện giữa mọi cặp đỉnh có đường đi không thỏa mãn, dù nhóm sáu đỉnh kia liên thông.
Bài luyện
Đơn đồ thị vô hướng có 4 đỉnh có nhiều nhất bao nhiêu cạnh?
Đúng. Có 4×3/2 cặp đỉnh khác nhau.
4 không phải số cặp đỉnh.
Đã đếm hai chiều thành hai cạnh khác nhau.
Đã tính cả tự nối và lặp chiều.
Lời giải
Mỗi cạnh nối một cặp đỉnh khác nhau, không phân biệt thứ tự. Có 4×3/2=6 cặp, nên tối đa 6 cạnh.
Đang học