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ị.