Lý thuyết đồ thị - Isomorphism
Một đồ thị có thể tồn tại ở các dạng khác nhau có cùng số đỉnh, số cạnh và cùng một kết nối cạnh. Đồ thị như vậy được gọi là đồ thị đẳng tích. Lưu ý rằng chúng tôi gắn nhãn các biểu đồ trong chương này chủ yếu nhằm mục đích tham khảo và nhận biết chúng với nhau.
Đồ thị đẳng hình
Hai đồ thị G 1 và G 2 được cho là đẳng tích nếu -
Số thành phần của chúng (đỉnh và cạnh) là như nhau.
Kết nối cạnh của họ vẫn được giữ lại.
Note- Tóm lại, trong số hai đồ thị đẳng tích, một đồ thị là phiên bản tinh chỉnh của đồ thị kia. Một đồ thị không có nhãn cũng có thể được coi là một đồ thị đẳng hình.
There exists a function ‘f’ from vertices of G1 to vertices of G2
[f: V(G1) ⇒ V(G2)], such that
Case (i): f is a bijection (both one-one and onto)
Case (ii): f preserves adjacency of vertices, i.e., if the edge {U, V} ∈ G1, then the
edge {f(U), f(V)} ∈ G2, then G1 ≡ G2.
Note
Nếu G 1 ≡ G 2 thì -
| V (G 1 ) | = | V (G 2 ) |
| E (G 1 ) | = | E (G 2 ) |
Trình tự bậc của G 1 và G 2 giống nhau.
Nếu các đỉnh {V 1 , V 2 , .. Vk} tạo thành một chu trình có độ dài K trong G 1 , thì các đỉnh {f (V 1 ), f (V 2 ),… f (Vk)} sẽ tạo thành một chu trình có độ dài K trong G 2 .
Tất cả các điều kiện trên là cần thiết để đồ thị G 1 và G 2 là đẳng tích, nhưng không đủ để chứng minh rằng đồ thị là đẳng tích.
(G 1 ≡ G 2 ) nếu và chỉ khi (G 1 - ≡ G 2 -) trong đó G 1 và G 2 là các đồ thị đơn giản.
(G 1 ≡ G 2 ) nếu ma trận kề của G 1 và G 2 giống nhau.
(G 1 ≡ G 2 ) nếu và chỉ khi các đồ thị con tương ứng của G 1 và G 2 (thu được bằng cách xóa một số đỉnh trong G1 và ảnh của chúng trong đồ thị G 2 ) là đẳng hình.
Example
Đồ thị nào sau đây là đồ thị đẳng tích?
Trong đồ thị G 3 , đỉnh 'w' chỉ có bậc 3, trong khi tất cả các đỉnh khác của đồ thị có bậc 2. Do đó G3 không đồng hình với G 1 hoặc G 2 .
Bổ sung G 1 và G 2 , bạn có -
Ở đây, (G 1 - ≡ G 2 -), do đó (G 1 ≡ G 2 ).
Đồ thị phẳng
Đồ thị 'G' được cho là phẳng nếu nó có thể được vẽ trên một mặt phẳng hoặc một mặt cầu sao cho không có hai cạnh nào cắt nhau tại một điểm không phải là đỉnh.
Example
Vùng
Mọi đồ thị phẳng đều chia mặt phẳng thành các vùng liên thông gọi là vùng.
Example
Mức độ của một vùng giới hạn r = deg(r) = Số cạnh bao quanh các vùng r.
deg(1) = 3
deg(2) = 4
deg(3) = 4
deg(4) = 3
deg(5) = 8
Mức độ của một vùng không giới hạn r = deg(r) = Số cạnh bao quanh các vùng r.
deg(R1) = 4
deg(R2) = 6
Trong đồ thị phẳng, các thuộc tính sau đây tốt:
Trong một đồ thị phẳng có 'n' đỉnh, tổng bậc của tất cả các đỉnh là:
Dựa theo Sum of Degrees of Regions/ Định lý, trong một đồ thị phẳng với 'n' vùng, Tổng độ của các vùng là -
Dựa vào định lý trên, bạn có thể rút ra các kết luận sau:
Trong một biểu đồ phẳng,
Nếu độ của mỗi vùng là K, thì tổng độ của các vùng là -
Nếu mức độ của mỗi vùng ít nhất là K (≥ K), thì
Nếu mức độ của mỗi vùng tối đa là K (≤ K), thì
Note - Giả sử rằng tất cả các vùng có mức độ như nhau.
Dựa theo Euler’s Formulae trên đồ thị phẳng,
Nếu đồ thị 'G' là một hình phẳng liên thông, thì
Nếu một đồ thị phẳng với các thành phần 'K', thì
Ở đâu, | V | là số đỉnh, | E | là số cạnh, và | R | là số vùng.
Bất bình đẳng cạnh đỉnh
Nếu 'G' là một đồ thị phẳng liên thông với độ của mỗi vùng ít nhất là 'K' thì,
| E | ≤ k / (k-2) {| v | - 2}
Bạn biết đấy, | V | + | R | = | E | + 2
K. | R | ≤ 2 | E |
K (| E | - | V | + 2) ≤ 2 | E |
(K - 2) | E | ≤ K (| V | - 2)
| E | ≤ k / (k-2) {| v | - 2}
Nếu 'G' là một đồ thị phẳng liên thông đơn giản, thì
|E| ≤ 3|V| − 6
|R| ≤ 2|V| − 4
Tồn tại ít nhất một đỉnh V • ∈ G sao cho deg (V) ≤ 5.
Nếu 'G' là một đồ thị phẳng liên thông đơn giản (có ít nhất 2 cạnh) và không có hình tam giác, thì
|E| ≤ {2|V| – 4}
Định lý Kuratowski
Một đồ thị 'G' là không phẳng nếu và chỉ khi 'G' có một đồ thị con là đồng dạng với K 5 hoặc K 3,3 .
Đồng tính
Hai đồ thị G 1 và G 2 được cho là đồng hình, nếu mỗi đồ thị này có thể nhận được từ cùng một đồ thị 'G' bằng cách chia một số cạnh của G có nhiều đỉnh hơn. Hãy xem ví dụ sau:
Chia cạnh 'rs' thành hai cạnh bằng cách thêm một đỉnh.
Các đồ thị dưới đây là đồng hình với đồ thị đầu tiên.
Nếu G 1 là đồng phân với G 2 , thì G là đồng cấu với G2 nhưng điều ngược lại không cần phải đúng.
Bất kỳ đồ thị nào có 4 đỉnh trở xuống đều là hình phẳng.
Bất kỳ đồ thị nào có 8 cạnh trở xuống đều là hình phẳng.
Một đồ thị hoàn chỉnh K n là phẳng khi và chỉ khi n ≤ 4.
Đồ thị lưỡng bội hoàn chỉnh K m, n là đồng phẳng khi và chỉ khi m ≤ 2 hoặc n ≤ 2.
Một đồ thị đơn giản không phẳng với số đỉnh tối thiểu là đồ thị hoàn chỉnh K 5 .
Đồ thị đơn giản không phẳng có số cạnh nhỏ nhất là K 3; 3 .
Đồ thị đa diện
Một đồ thị phẳng liên thông đơn giản được gọi là đồ thị đa diện nếu tung độ của mỗi đỉnh là ≥ 3, tức là deg (V) ≥ 3 ∀ V ∈ G.
3 | V | ≤ 2 | E |
3 | R | ≤ 2 | E |