Các khái niệm cơ bản về đồ thị (phần 1)

· Uncategorized, Đồ thị

Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Được mô tả hình thức:

G = (V,E)

V gọi là tập các đỉnh (Vertices)

E gọi là tập các cạnh (Edges)

Có thể coi E là tập các cặp (u,v) với u và v là hai đỉnh của V

Cho đồ thị G = (V, E)

G gọi là đơn đồ thị nếu giữa hai đỉnh u, v của V có nhiều nhất là một cạnh trong E nối từ u tới v

G gọi là đa đồ thị nếu giữa hai đỉnh u, v của V có thể có nhiều hơn một cạnh trong E nối từ u tới v (hiển nhiên đơn đồ thị cũng là đa đồ thị)

G gọi là đồ thị vô hướng (undirected graph) nếu các cạnh trong E không định hướng, tức là các cạnh nối hai đỉnh u, v bất kỳ cũng là cạnh nối hai đỉnh v, u. Hay nói cách khác tập E gồm các cặp (u,v) không tính thứ tự

G gọi là đồ thị có hướng (directed graph) nếu các cạnh trong E là có định hướng, tức là có thể có cạnh nối từ đỉnh u tới đỉnh v nhưng chưa chắc đã có cạnh nối từ đỉnh v đến đỉnh u. Hay nói cách khác, tập E gồm các cặp (u,v) có tính tứ tự. Trong đồ thị có hướng các cạnh được gọi là các cung. Đồ thị vô hướng cũng có thể coi là đồ thị có hướng nếu như ta coi cạnh nối hai đỉnh (u,v) bất kỳ tương đương với hai cung (u,v) và (v,u).

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: