Giới thiệu về Lý thuyết đồ thị

I. Khái niệm về đồ thị

1. Sơ lược về Lý thuyết đồ thị

Trong Toán học và Tin học, Lý thuyết đồ thị tập trung nghiên cứu về một đối tượng cơ bản là đồ thị – một đối tượng có tính ứng dụng rất cao trong thực tế. Mô hình đồ thị xuất hiện xung quanh ta, trong nhiều lĩnh vực của cuộc sống, như giao thông, cấu trúc website,…

Mô hình bài toán 7 cây cầu ở Königsberg

Người đặt nền móng cho sự phát triển của Lý thuyết đồ thị là Leonhard Euler – nhà toán học người Thụy Sĩ. Thông qua việc đưa ra lời giải cho bài toán 77 cây cầu ở Königsberg vào năm 17361736, ông đã chính thức khai sinh lý thuyết đồ thị.

Một cách trừu tượng hóa, đồ thị là một tập các đối tượng được gọi là các đỉnh (hoặc nút) được nối với nhau bằng các cạnh (hoặc cung) và được biểu diễn theo nhiều cách khác nhau trong Toán học và Tin học.

2. Định nghĩa và phân loại đồ thị

Một đồ thị là một cấu trúc rời rạc gồm tập hợp các đỉnh và các cạnh nối giữa các đỉnh đó. Có thể mô tả đồ thị theo cách hình thức như sau:

G=(V,E)G=(V,E)

tức là đồ thị GG có tập các đỉnh là VV, tập các cạnh là EE. Có thể hiểu EE là tập hợp các cặp (u,v)(u, v) với uuvv là hai đỉnh thuộc VV.

Có thể phân loại đồ thị GG theo tính chất của tập cạnh như sau:

  • GG được gọi là đơn đồ thị nếu như giữa hai đỉnh (u,v)(u, v) của VV có nhiều nhất một cạnh trong EE nối từ uu tới vv.
  • GG được gọi là đa đồ thị nếu như giữa hai đỉnh (u,v)(u, v) của VV có thể có nhiều hơn 11 cạnh nối trong EE nối từ uu tới vv. Hiển nhiên đơn đồ thị cũng là đa đồ thị.
  • GG được gọi là đồ thị vô hướng (undirected graph) nếu như các cạnh trong EE là không định hướng, tức là cạnh (u,v)(u, v)cạnh hai chiều.
  • GG được gọi là đồ thị có hướng (directed graph) nếu như các cạnh trong EE là có định hướng, tức là có thể tồn tại cạnh nối từ u tới v nhưng chưa chắc đã tồn tại cạnh nối từ v tới u. Trên đồ thị có hướng, các cạnh sẽ đượ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 (u,v)(u, v) bất kỳ tương ứng với hai cung (u→v)(urightarrow v)(v→u)(v rightarrow u).

II. Các khái niệm trên đồ thị

1. Cạnh liên thuộc, đỉnh kề, bậc và khuyên

Đối với đồ thị vô hướng G=(V,E),G=(V, E), xét cạnh e=(u,v)∈Ee = (u, v) in E. Ta nói rằng hai đỉnh uuvvkề nhau (adjacent), và cạnh ee này liên thuộc (incident) với hai đỉnh uuvv.

Với một đinh u thuộc đồ thị, định nghĩa bậc (degree), ký hiệu deg(u)deg(u) là số cạnh liên thuộc với uu. Trên đơn đồ thị, số cạnh liên thuộc với uu cũng chính là số đỉnh kề với uu.

Định lý 1

Giả sử G=(V,E)G=(V, E) là đồ thị vô hướng với MM cạnh khi đó tổng tất cả các bậc đỉnh trong VV sẽ bằng 2M2M.

∑v∈Vdeg(v)=2Msum_{v in V} deg(v)=2M

Chứng minh: Khi lấy tổng tất cả các bậc đỉnh, tức là mỗi cạnh e=(u,v)e=(u, v) bất kỳ sẽ được tính một lần trong deg(u)deg(u) và một lần trong deg(v)deg(v). Từ đó suy ra điều phải chứng minh.

Hệ quả:Trên đồ thị vô hướng, số đỉnh bậc lẻ là một số chẵn.

Đối với đồ thị có hướng G=(V,E)G=(V, E), xét một cung e=(u→v)∈Ee=(u rightarrow v) in E. Khi đó ta nói đỉnh u nối tới đỉnh vđỉnh v nối từ đỉnh u. Đỉnh uu được gọi là đỉnh đầu, đỉnh vv được gọi là đỉnh cuối của cung ee.

Với mỗi đỉnh u trong đồ thị có hướng, định nghĩa: Bán bậc ra (out-degree) của đỉnh uu, kí hiệu deg+(u)deg^+(u) là số cung đi ra khỏi nó; Bán bậc vào (in-degree) của đỉnh uu, kí hiệu deg−(u)deg^-(u) là số cung đi vào nó.

Định lý 2

Giả sử G=(V,E)G=(V, E) là đồ thị có hướng với M cung, khi đó tổng tất cả các bán bậc ra bằng tổng tất cả các bán bậc vào và bằng MM:

∑v∈Vdeg+(v)=∑v∈Vdeg−(v)=Msum_{v in V} deg^+(v)=sum_{v in V} deg^-(v)=M

Chứng minh: Khi lấy tổng tất cả các bán bậc ra hoặc bán bậc vào, mỗi cung (u→v)(urightarrow v) bất kỳ sẽ được tính đúng một lần trong deg+(u)deg^+(u) và cũng được tính đúng một lần trong deg−(v)deg^-(v). Từ đó suy ra điều phải chứng minh.

Ngoài ra, trên đồ thị có hướng hoặc vô hướng, trong một số trường hợp có thể có những cạnh nối một đỉnh với chính nó. Cạnh này được gọi là khuyên của đồ thị, và trong trường hợp này, thì các cạnh nối hai đỉnh phân biệt sẽ được gọi là các liên kết để tránh nhầm lẫn.

Đồ thị có khuyên ở đỉnh 3

2. Đường đi và chu trình

Một đường điPP độ dài kk từ đỉnh v0v_0 tới đỉnh vkv_k là tập đỉnh {v0,v1,v2,…,vk}{v_0, v_1, v_2,…, v_k} sao cho (vi−1,vi)∈E,∀i:1≤i≤k(v_{i – 1},v_i) in E, forall i: 1 le i le k. Khi đó ta nói đường đi này bao gồm các đỉnh {v0,v1,v2,…,vk}{v_0, v_1, v_2,…, v_k} và các cạnh {(v0,v1),(v1,v2),…,(vk−1,vk)}{(v_0, v_1), (v_1, v_2), …, (v_{k – 1}, v_k)}; và v0v_0 đến được vkv_k thông qua đường đi PP.

Đường đi được gọi là đường đi đơn giản (simple path) nếu tất cả các đỉnh trên đường đi đó đều phân biệt. Đường đi được gọi là đường đi đơn nếu như không có cạnh nào trên đường đi đó đi qua hơn một lần.

Một đường đi con (subpath)P′P’ của PP là một đoạn liên tục các đỉnh và cạnh dọc theo đường đi PP.

Đường đi PP gọi là chu trình (circuit) nếu như v0=vkv_0=v_k. Chu trình PP gọi là chu trình đơn giản (simple circuit) nếu như {v1,v2,…,vk}{v_1, v_2,…, v_k} đôi một khác nhau. Chu trình mà trong đó không có cạnh nào đi qua hơn một lần được gọi là chu trình đơn.

3. Tính liên thông của đồ thị

Đối với đồ thị vô hướng G=(V,E)G=(V, E) thì GG được gọi là liên thông nếu như với mọi cặp đỉnh phân biệt (u,v)(u, v), ta đều có uu đến được vv (đồng nghĩa với vv cũng đến được uu).

Đối với đồ thị có hướng G=(V,E)G=(V, E):

  • GG được gọi là liên thông mạnh (strongly connected) nếu với mọi cặp đỉnh phân biệt (u,v)(u, v), ta có uu đến được vvvv đến được uu.
  • GG được gọi là liên thông yếu (weakly connected) nếu như đồ thị vô hướng nền của nó là liên thông (tức là hủy bỏ chiều của các cạnh trên đồ thị).
  • GG được gọi là liên thông một phần (unilaterally connected) nếu như với mọi cặp đỉnh phân biệt (u,v),(u, v), có ít nhất một đỉnh đến được đỉnh còn lại.

III. Tài liệu tham khảo

Nguồn: viblo.asia

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *