LÝ THUYẾT ĐỒ THỊ C++

     
I. Có mang về đồ thị

1. Sơ lược về định hướng đồ thị

Trong Toán học với Tin học, Lý thuyết đồ thị tập trung nghiên cứu về một đối tượng người dùng cơ bản là vật thị - một đối tượng người sử dụng có tính ứng dụng rất cao trong thực tế. Quy mô đồ thị mở ra xung xung quanh ta, trong nhiều nghành của cuộc sống, như giao thông, kết cấu website,...

Bạn đang xem: Lý thuyết đồ thị c++

*

Mô hình vấn đề 7 cây ước ở Königsberg

Người để nền móng cho sự phát triển của triết lý đồ thị là Leonhard Euler - đơn vị toán học bạn Thụy Sĩ. Trải qua việc đưa ra giải thuật cho vấn đề 777 cây mong ở Königsberg vào năm 173617361736, ông đã bằng lòng khai sinh lý thuyết đồ thị.

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

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

Một trang bị thị là một cấu tạo rời rạc bao gồm tập hợp các đỉnh và những cạnh nối giữa những đỉnh đó. Rất có thể mô tả đồ vật thị theo cách bề ngoài như sau:

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

tức là đồ thị GGG tất cả tập các đỉnh là VVV, tập những cạnh là EEE. Có thể hiểu EEE là tập hợp những cặp (u,v)(u, v)(u,v) cùng với uuu với vvv là nhì đỉnh ở trong VVV.

Có thể phân loại đồ thị GGG theo đặc thù của tập cạnh như sau:

GGG được call là đơn đồ thị ví như như thân hai đỉnh (u,v)(u, v)(u,v) của VVV có nhiều nhất một cạnh vào EEE nối từ uuu cho tới vvv.GGG được hotline là đa vật thị nếu như giữa hai đỉnh (u,v)(u, v)(u,v) của VVV có thể có tương đối nhiều hơn 111 cạnh nối trong EEE nối từ uuu cho tới vvv. Hiển nhiên đơn đồ thị cũng chính là đa đồ thị.GGG được hotline là đồ thị vô hướng (undirected graph) trường hợp như những cạnh trong EEE là không định hướng, tức là cạnh (u,v)(u, v)(u,v) là cạnh nhị chiều.GGG được call là đồ thị tất cả hướng (directed graph) ví như như những cạnh vào EEE là gồm định hướng, có nghĩa là có thể lâu dài cạnh nối tự u tới v nhưng lại chưa có thể đã sống thọ cạnh nối tự v cho tới u. Trên thứ thị có hướng, các cạnh sẽ được gọi là các cung. Đồ thị vô phía cũng có thể coi là trang bị thị bao gồm hướng, ví như như ta coi cạnh (u,v)(u, v)(u,v) bất kỳ tương ứng với nhị cung (u→v)(u ightarrow v)(u→v) và (v→u)(v ightarrow u)(v→u).

*

II. Các khái niệm trên vật dụng thị

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

Đối với thiết bị thị vô phía G=(V,E),G=(V, E),G=(V,E), xét cạnh e=(u,v)∈Ee = (u, v) in Ee=(u,v)∈E. Ta nói rằng hai đỉnh uuu với vvv kề nhau (adjacent), với cạnh eee này liên nằm trong (incident) với hai đỉnh uuu và vvv.

Với một đinh u thuộc thiết bị thị, tư tưởng bậc (degree), cam kết hiệu deg(u)deg(u)deg(u) là số cạnh liên nằm trong với uuu. Trên 1-1 đồ thị, số cạnh liên nằm trong với uuu cũng chính là số đỉnh kề với uuu.

Định lý 1

Giả sử G=(V,E)G=(V, E)G=(V,E) là đồ thị vô phía với MMM cạnh lúc đó tổng tất cả các bậc đỉnh trong VVV sẽ bằng 2M2M2M.

∑v∈Vdeg(v)=2Msum_v in V deg(v)=2Mv∈V∑​deg(v)=2M

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

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

Xem thêm: 5 Cách Kiểm Tra Nợ Cước Viettel Trả Sau Viettel, Mobifone, Vinaphone

Đối với trang bị thị có hướng G=(V,E)G=(V, E)G=(V,E), xét một cung e=(u→v)∈Ee=(u ightarrow v) in Ee=(u→v)∈E. Khi đó ta nói đỉnh u nối cho tới đỉnh v với đỉnh v nối trường đoản cú đỉnh u. Đỉnh uuu được điện thoại tư vấn là đỉnh đầu, đỉnh vvv được call là đỉnh cuối của cung eee.

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

Định lý 2

Giả sử G=(V,E)G=(V, E)G=(V,E) là đồ thị được bố trí theo hướng với M cung, lúc đó tổng toàn bộ các phân phối bậc ra bằng tổng tất cả các bán bậc vào và bởi MMM:

∑v∈Vdeg+(v)=∑v∈Vdeg−(v)=Msum_v in V deg^+(v)=sum_v in V deg^-(v)=Mv∈V∑​deg+(v)=v∈V∑​deg−(v)=M

Chứng minh: Khi rước tổng tất cả các phân phối bậc ra hoặc cung cấp bậc vào, từng cung (u→v)(u ightarrow v)(u→v) bất kỳ sẽ được tính đúng một đợt trong deg+(u)deg^+(u)deg+(u) và cũng rất được tính đúng một lượt trong deg−(v)deg^-(v)deg−(v). Từ kia suy ra điều nên 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à vào 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 răn ở đỉnh 3

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

Một đường đi PPP độ nhiều năm kkk trường đoản cú đỉnh v0v_0v0​ cho tới đỉnh vkv_kvk​ là tập đỉnh v0,v1,v2,...,vkv_0, v_1, v_2,..., v_kv0​,v1​,v2​,...,vk​ làm thế nào cho (vi−1,vi)∈E,∀i:1≤i≤k(v_i - 1,v_i) in E, forall i: 1 le i le k(vi−1​,vi​)∈E,∀i:1≤i≤k. Khi ấy ta nói đường đi này bao gồm các đỉnh v0,v1,v2,...,vkv_0, v_1, v_2,..., v_kv0​,v1​,v2​,...,vk​ 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)(v0​,v1​),(v1​,v2​),...,(vk−1​,vk​); và v0v_0v0​ cho được vkv_kvk​ trải qua đường đi PPP.

Đường đi được điện thoại tư vấn là đường đi đơn giản và dễ dàng (simple path) nếu toàn bộ các đỉnh trê tuyến phố đi đó đều phân biệt. Đường đi được hotline là đường đi đơn ví như như không tồn tại cạnh nào trên đường đi đó đi qua hơn một lần.

Một đường đi bé (subpath) P′P"P′ của PPP là 1 trong những đoạn liên tiếp các đỉnh với cạnh dọc theo đường đi PPP.

Đường đi PPP gọi là chu trình (circuit) nếu như như v0=vkv_0=v_kv0​=vk​. Quy trình PPP hotline là chu trình đơn giản và dễ dàng (simple circuit) giả dụ như v1,v2,...,vkv_1, v_2,..., v_kv1​,v2​,...,vk​ song một khác nhau. Chu trình mà trong đó không tồn tại cạnh nào đi qua hơn một đợt được gọi là chu trình đơn.

Xem thêm: Hướng Dẫn Sử Dụng Tai Nghe Airpods Từ A Đến Z Chi Tiết Nhất, Cách Sử Dụng Airpods Cơ Bản Cho Người Mới

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

Đối với vật thị vô hướng G=(V,E)G=(V, E)G=(V,E) thì GGG được hotline là liên thông trường hợp như với đa số cặp đỉnh khác nhau (u,v)(u, v)(u,v), ta đều phải có uuu mang đến được vvv (đồng nghĩa với vvv cũng mang đến được uuu).

Đối với vật thị được bố trí theo hướng G=(V,E)G=(V, E)G=(V,E):

GGG được gọi là liên thông táo bạo (strongly connected) nếu với đa số cặp đỉnh sáng tỏ (u,v)(u, v)(u,v), ta bao gồm uuu cho được vvv và vvv mang đến được uuu.GGG được điện thoại tư vấn là liên thông yếu hèn (weakly connected) nếu như đồ gia dụng thị vô hướng nền của nó là liên thông (tức là hủy vứt chiều của những cạnh trên đồ dùng thị).GGG được điện thoại tư vấn là liên thông 1 phần (unilaterally connected) nếu như với mọi cặp đỉnh sáng tỏ (u,v),(u, v),(u,v), có ít nhất một đỉnh cho được đỉnh còn lại.III. Tư liệu tham khảo