tailieunhanh - CHƯƠNG 5: ĐỒ THỊ

Một đồ thị G bao gồm một tập hợp V các đỉnh và một tập hợp E các cạnh, ký hiệu G=(V,E). • Các đỉnh còn được gọi là nút (node) hay điểm (point). Các cạnh nối giữa hai đỉnh, hai đỉnh này có thể trùng nhau. • Hai đỉnh có cạnh nối nhau gọi là hai đỉnh kề (adjacency). Một cạnh nối giữa hai đỉnh v, w có thể coi như là một cặp điểm (v,w). • Nếu cặp này có thứ tự thì ta có cạnh có thứ tự, ngược lại thì cạnh không có thứ tự | CANTHO UNIVERSITY CHƯƠNG 5 Đồ THỊ Nguyễn Văn Linh Khoa CNTT-TT Đại học Cần Thơ nvlinh@ Nguyễn Văn Linh noidung CANTHO UNIVERSITY Các khái niệm Biểu diễn đồ thị Các phép duyệt trên đồ thị Các bài toán trên đồ thị Nguyễn Văn Linh CÁC KHÁI NIỆM 1 CANTHO UNIVERSITY Một đồ thị G bao gồm một tập hợp V các đỉnh và một tập hợp E các cạnh ký hiệu G V E . Các đỉnh còn được gọi là nút node hay điểm point . Các cạnh nối giữa hai đỉnh hai đỉnh này có thể trùng nhau. Hai đỉnh có cạnh nối nhau gọi là hai đỉnh kề adjacency . Một cạnh nối giữa hai đỉnh v w có thể coi như là một cặp điểm v w . Nếu cặp này có thứ tự thì ta có cạnh có thứ tự ngược lại thì cạnh khống có thứ tự. Nếu các cạnh trong đồ thị G có thứ tự thì G gọi là đồ thị có hướng directed graph . Nếu các cạnh trong đồ thị G không có thứ tự thì đồ thị G là đồ thị vô hướng undirected graph . Nguyễn Văn Linh .