Bài giảng chương 13: Đồ thị

Một đồ thị (graph) G gồm một tập V chứa các đỉnhcủa đồ thị, và tập E chứa các cặp đỉnh khác nhau từ V. Các cặp đỉnh này được gọi là các cạnh của G. Nếu e= (?, µ) là một cạnh có hai đỉnh ? và µ, thì chúng ta gọi ? và µnằm trên e, và enối với ?và µ. Nếu các cặp đỉnh không có thứ tự, G được gọi là đồ thị vô hướng (undirected graph), ngược lại, G được gọi là đồ thị có hướng (directed graph). Thông thường đồ thị có hướng được gọi tắt là digraph, còn từ graphthường mang nghĩa là đồ thị vô hướng. Cách tự nhiên để vẽ đồ thị là biểu diễn các đỉnh bằng các điểm hoặc vòng tròn, và các cạnh bằng các đường thẳng hoặc các cung nối các đỉnh. Đối với đồ thị có hướng thì các đường thẳng hay các cung cần có mũi tên chỉ hướng. Hình 13.1 minh họa một số ví dụ về đồ thị.

pdf26 trang | Chia sẻ: haohao89 | Lượt xem: 1799 | Lượt tải: 1download
Bạn đang xem trước 20 trang tài liệu Bài giảng chương 13: Đồ thị, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Tài liệu liên quan