Bài giảng Thuật toán ứng dụng: Đồ thị cung cấp cho người học những kiến thức như: Khái niệm đồ thị; Biểu diễn đồ thị trong máy tính; Duyệt đồ thị; Đường đi ngắn nhất; Bài tập. Mời các bạn cùng tham khảo! | THUẬT TOÁN ỨNG DỤNG Đồ thị Nội dung 1. Khái niệm đồ thị 2. Biểu diễn đồ thị trong máy tính 3. Duyệt đồ thị 4. Đường đi ngắn nhất 5. Bài tập TRƯƠNG XUÂN NAM 2 Phần 1 Khái niệm đồ thị TRƯƠNG XUÂN NAM 3 Khái niệm đồ thị Đồ thị Sự trừu tượng hóa các đối tượng và các mối liên hệ giữa chúng trong thực tế Đường đi giữa các thành phố Đường nối mạng giữa các thiết bị kết nối Đường điện trong khu vực Mối quan hệ giữa các cá nhân trên mạng xã hội Các đối tượng các đỉnh Các mối quan hệ kết nối các cạnh cung TRƯƠNG XUÂN NAM 4 Khái niệm đồ thị Đồ thị các đỉnh các cung nối giữa chúng G V E G Graph đồ thị V Vertices đỉnh E Edges cung Tập V tập các đỉnh thường đánh số từ 1 đến n hoặc từ 0 đến n-1 Tập E tập các cung nối giữa hai đỉnh một cung là một cặp u v có thể u v Đồ thị có hướng cung u v và cung v u không có mối liên hệ gì đặc biệt thường nói gọi tắt là đồ thị TRƯƠNG XUÂN NAM 5 Khái niệm đồ thị Đa đồ thị giữa các cặp u v có thể có nhiều hơn 1 cung nối chúng Đơn đồ thị giữa các cặp u v chỉ có tối đa 1 cung Đồ thị vô hướng cung u v và cung v u là một không phân biệt Trường hợp này người ta dùng từ cạnh u v để chỉ ý nghĩa u v và v u là tương đương TRƯƠNG XUÂN NAM 6 Độ đo về đỉnh cung cạnh Nếu có cạnh u v thì hai đỉnh u và v được gọi là kề nhau đỉnh liền kề Cạnh e u v gọi là liên thuộc hay phụ thuộc đỉnh u và cả đỉnh v đương nhiên Bậc của đỉnh v deg v số cạnh phụ thuộc vào v số đỉnh liền kề với v Trong đồ thị vô hướng số đỉnh bậc lẻ luôn chẵn Cung e u v e gọi là cung ra khỏi u và là cung đi vào v Số cung ra của v là deg v số cung vào v là deg- v Tổng các deg và def- luôn bằng nhau và bằng số cung Cung u v có thể có trọng số khi đó G là đồ thị trọng số TRƯƠNG XUÂN NAM 7 Đường đi và chu trình Đường đi từ u đến v bắt đầu từ u liên tiếp di chuyển qua các đỉnh kề để đến v Đường đi không tự cắt từ u đến v quá trình di chuyển từ u đến v không thăm lại một đỉnh đã đi qua thường nói về đường đi ta nói về đường đi không tự cắt Chu trình đường đi từ u trở về chính nó Một đường đi chu trình .
