Rate this post

Đồ thị G bao gồm hai thứ:

1. Một tập hợp V = V (G) có các phần tử đượ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à các cạnh của G.

3. Chúng ta biểu thị một đồ thị như vậy bởi G (V, E) các đỉ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 liên quan:

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 các bậc của tất cả các đỉnh là chẵn đối với đồ thị được hiển thị trong hình:

Bài giải: Tổng bậc của tất cả các đỉ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 đó, 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 giản không phải là cơ bản từ V1 đến V6.

Một con đường không đơn giản và bắt đầu từV2.

Một mạch đơn giản bắt đầu từ V1

Một mạch không đơn giản và bắt đầu từ V2.

Đáp án:

Một đường dẫn đơn giả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 giả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 giản và bắt đầu từ V2.

V2, V3, V4, V5, V3, V4, V6.

Một đoạn mạch đơn giản bắt đầu từ V1.

V1, V2, V4, V6, V5, V3, V1

Một mạch không đơn giản và bắt đầu 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 các cạnh nhỏ nhất sao cho việc loại bỏ tập hợp đó, làm ngắt kết nối đồ thị trong khi việc loại bỏ 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 kết nối .

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 kết nối. Trong khi sau khi loại bỏ 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 kết nối.

Đ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 kết nối. Đồ thị con G-v nhận được bằng cách xóa đỉnh v khỏi đồ thị G và cũng xóa toàn bộ sự cố các cạnh trên v.

Ví dụ: Hãy xem xét biểu đồ được hiển thị trong hình. Xác định các đồ thị con

(i) G-v1 (ii) G-v3 (iii) G-v5