Rate this post
Đồ thị G gồm có hai thứ :
1. Một tập hợp V = V ( G ) có những thành phần được gọi là đỉnh, điểm hay nút của G .
2. Tập hợp E = E ( G ) gồm một cặp đỉnh phân biệt không có thứ tự được gọi là những cạnh của G .
3. Chúng ta bộc lộ một đồ thị như vậy bởi G ( V, E ) những đỉnh u và v được cho là kề nhau nếu có một cạnh e = { u, v } .
4. Trong trường hợp như vậy u và v được gọi là điểm cuối của e = { u, v } và e được cho là nối u và v .
Các bài viết tương quan :
Tóm Tắt
Bậc của một đỉnh
Bậc của đỉnh là số cạnh của đỉnh v. Vòng lặp tự được tính hai lần. Bậc của một đỉnh được ký hiệu là d ( v ) .
Ví dụ 1 : Hãy xem xét đồ thị G được hiển thị trong hình. Xác định tung độ của mỗi đỉnh .
Bài giải : Bậc của mỗi đỉnh như sau :
d ( a ) = 3 ; d ( b ) = 5 ; d ( c ) = 2 ; d ( d ) = 2 .
Ví dụ 2 : Xác minh rằng tổng những bậc của toàn bộ những đỉnh là chẵn so với đồ thị được hiển thị trong hình :
Bài giải : Tổng bậc của tổng thể những đỉnh là :
= d ( v1 ) + d ( v2 ) + d ( v3 ) + d ( v4 ) + d ( v5 ) + d ( v6 ) + d ( v7 ) + d ( v8 )
= 2 + 3 + 3 + 3 + 3 + 4 + 2 + 2 = 22, là số chẵn .
Ví dụ 3 : Xác minh rằng có số lượng đỉnh có độ lẻ chẵn trong biểu đồ được hiển thị trong hình :
Bài giải : Số đỉnh có bậc lẻ là 8 và mỗi đỉnh có bậc ba trong đồ thị trên. Do đó, tất cả chúng ta có số đỉnh chẵn có bậc lẻ .
Đường đi
Đường đi có độ dài n là một dãy gồm n + 1 đỉnh của đồ thị, trong đó mỗi cặp đỉnh là một cạnh của đồ thị .
Đường dẫn đơn giản: Đường đi được gọi là đường đơn giản nếu không có cạnh nào được lặp lại trong đường đi, tức là tất cả các đỉnh là khác biệt ngoại trừ đỉnh đầu tiên bằng với đỉnh cuối cùng.
Một đường dẫn sơ cấp: Đường đi được gọi là đường sơ cấp nếu không có đỉnh nào được lặp lại trong đường dẫn, tức là tất cả các đỉnh đều khác biệt.
Mạch hoặc Đường đi kín: Đường mạch hoặc đường dẫn kín là một đường dẫn trong đó bắt đầu và kết thúc tại cùng một đỉnh, tức là v0 = vn.
Đường dẫn mạch đơn giản: Mạch điện đơn giản là một đường dẫn đơn giản là một mạch điện.
Ví dụ : Hãy xem xét biểu đồ được hiển thị trong hình : Cho một ví dụ sau :
Một đường dẫn đơn giản từ V1 đến V6.
Một đường dẫn sơ cấp từ V1 đến V6 .
Một con đường đơn thuần không phải là cơ bản từ V1 đến V6 .
Một con đường không đơn thuần và mở màn từV2 .
Một mạch đơn thuần khởi đầu từ V1
Một mạch không đơn thuần và khởi đầu từ V2 .
Đáp án :
Một đường dẫn đơn thuần từ V1 đến V6 .
V1, V2, V3, V4, V5, V6 .
Một đường dẫn sơ cấp từ V1 đến V6 .
V1, V2, V3, V5, V4, V6 .
Một con đường đơn thuần không phải là cơ bản từ V1 đến V6 .
V1, V2, V3, V5, V2, V4, V6 .
Một con đường không đơn thuần và khởi đầu từ V2 .
V2, V3, V4, V5, V3, V4, V6 .
Một đoạn mạch đơn thuần khởi đầu từ V1 .
V1, V2, V4, V6, V5, V3, V1
Một mạch không đơn thuần và mở màn từ V2 .
V2, V3, V1, V2, V5, V4, V2 .
- Đỉnh mặt dây chuyền: Một đỉnh có bậc một được gọi là Đỉnh mặt dây chuyền.
- Cạnh mặt dây chuyền: Cạnh duy nhất nối với đỉnh mặt dây chuyền được gọi là Cạnh mặt dây chuyền.
- Đỉnh lẻ: Một đỉnh có bậc lẻ được gọi là đỉnh lẻ.
- Đỉnh chẵn: Đỉnh có tung độ được gọi là đỉnh chẵn.
- Cạnh kề: Một cạnh được gọi là sự cố với các đỉnh được nối.
- Các đỉnh liền kề: Hai đỉnh được gọi là kề nhau nếu một cạnh liên kết chúng. Nếu có một cạnh (u, v), thì ta có thể nói đỉnh u là kề với đỉnh v, và đỉnh v là kề với đỉnh u.
Ví dụ : Hãy xem xét biểu đồ như trong hình :
Xác định những điều sau :
- Dọc mặt dây chuyền
- Viền mặt dây chuyền
- Các đỉnh lẻ
- Dọc chẵn
- Cạnh kề
- Dọc liền kề
- Đỉnh V5 là đỉnh mặt dây chuyền.
- Cạnh (V4, V5) hoặc e5 là cạnh mặt dây chuyền.
- Các đỉnh V3 và V5 là các đỉnh lẻ.
- Các đỉnh V1, V2 và V4 là các đỉnh chẵn.
- Cạnh e1 là một sự cố trên V1 và V2.
- Cạnh e2 là một sự cố trên V1 và V3.
- Cạnh e3 là sự cố trên V2 và V3.
- Cạnh e4 là một sự cố trên V3 và V4.
- Cạnh e5 là một sự cố trên V4 và V5.
- Đỉnh V1 tiếp giáp với V2 và V3.
- Đỉnh V2 tiếp giáp với V1 và V2.
- Đỉnh V3 tiếp giáp với V1 và V4
- Đỉnh V4 tiếp giáp với V3 và V5
- Đỉnh V5 kề với V4.
Self-Loop: Một vòng lặp tự là một cạnh e nếu nó có cùng điểm cuối.
Đồ thị trong hình chứa vòng lặp tự tại đỉnh b, tức là, e = ( b, b ) .
Đỉnh cô lập : Một đỉnh có bậc 0 được gọi là đỉnh cô lập .
Tập cắt : Xét một đồ thị G = ( V, E ). Một tập cắt cho G là tập những cạnh nhỏ nhất sao cho việc vô hiệu tập hợp đó, làm ngắt liên kết đồ thị trong khi việc vô hiệu bất kể tập hợp con thích hợp nào của tập hợp này sẽ để lại một đồ thị con được liên kết .
Ví dụ : Hãy xem xét biểu đồ được hiển thị trong hình. Xác định tập hợp cắt cho nhóm này .
Lời giải : Đối với đồ thị này, tập cạnh { ( V1, V5 ), ( V7, V5 ) } là tập cắt. Sau khi xóa tập hợp, chúng tôi đã để lại với một đồ thị con bị ngắt liên kết. Trong khi sau khi vô hiệu bất kể tập hợp con thích hợp nào của nó, chúng tôi đã để lại với một đồ thị con được liên kết .
Điểm cắt hoặc đỉnh cắt : Xét đồ thị G = ( V, E ). Điểm cắt của đồ thị G là đỉnh v sao cho G-v có nhiều thành phần liên thông hơn G hoặc bị ngắt liên kết. Đồ thị con G-v nhận được bằng cách xóa đỉnh v khỏi đồ thị G và cũng xóa hàng loạt sự cố những cạnh trên v .
Ví dụ : Hãy xem xét biểu đồ được hiển thị trong hình. Xác định những đồ thị con
( i ) G-v1 ( ii ) G-v3 ( iii ) G-v5
- Biểu đồ con G-v1 được hiển thị trong hình
- Đồ thị con G-v3 được hiển thị trong hình
- Đồ thị con G-v5 được hiển thị trong hình
Cầu ( Cut Edges ) : Xét đồ thị G = ( V, E ). Một cầu cho đồ thị G, là một cạnh e sao cho G-e có nhiều thành phần liên thông hơn G hoặc ngắt liên kết .
Ví dụ : Hãy xem xét biểu đồ được hiển thị trong hình. Xác định những đồ thị con
(i) G-e1 (ii) G-e3 (iii) G-e4
Biểu đồ con G-e1 được hiển thị trong hình
Biểu đồ con G-e3 được hiển thị trong hình
Biểu đồ con G-e4 được hiển thị trong hình
Source: https://final-blade.com
Category : Tiền Điện Tử – Tiền Ảo
