Biểu đồ & Mô hình Đồ thị
Phần trước đã đưa ra các công cụ khác nhau để lập luận, chứng minh và giải quyết vấn đề. Trong phần này, chúng ta sẽ nghiên cứu các cấu trúc rời rạc tạo cơ sở cho việc hình thành nhiều bài toán thực tế.
Hai cấu trúc rời rạc mà chúng ta sẽ đề cập là đồ thị và cây. Đồ thị là một tập hợp các điểm, được gọi là nút hoặc đỉnh, được nối với nhau bởi một tập hợp các đường được gọi là các cạnh. Nghiên cứu đồ thị, hoặcgraph theory là một phần quan trọng của một số ngành trong lĩnh vực toán học, kỹ thuật và khoa học máy tính.
Đồ thị là gì?
Definition - Một đồ thị (được ký hiệu là $ G = (V, E) $) bao gồm tập các đỉnh hoặc nút V không rỗng và tập các cạnh E.
Example - Chúng ta hãy xem xét, một Đồ thị là $ G = (V, E) $ trong đó $ V = \ lbrace a, b, c, d \ rbrace $ và $ E = \ lbrace \ lbrace a, b \ rbrace, \ lbrace a , c \ rbrace, \ lbrace b, c \ rbrace, \ lbrace c, d \ rbrace \ rbrace $
Degree of a Vertex - Bậc của đỉnh V của đồ thị G (ký hiệu là deg (V)) là số cạnh tiếp giáp với đỉnh V.
Đỉnh | Trình độ | Chẵn lẻ |
---|---|---|
a | 2 | cũng |
b | 2 | cũng |
c | 3 | kỳ quặc |
d | 1 | kỳ quặc |
Even and Odd Vertex - Nếu tung độ của đỉnh là chẵn thì đỉnh đó được gọi là đỉnh chẵn và nếu tung độ của đỉnh là lẻ thì đỉnh đó được gọi là đỉnh lẻ.
Degree of a Graph- Bậc của một đồ thị là tung độ đỉnh lớn nhất của đồ thị đó. Đối với đồ thị trên tung độ của đồ thị là 3.
The Handshaking Lemma - Trong một đồ thị, tổng tất cả các tung độ của tất cả các đỉnh bằng hai lần số cạnh.
Các loại đồ thị
Có nhiều loại đồ thị khác nhau, chúng ta sẽ tìm hiểu trong phần sau.
Đồ thị rỗng
Một đồ thị rỗng không có cạnh. Đồ thị rỗng của $ n $ đỉnh được ký hiệu là $ N_n $
Đồ thị đơn giản
Một đồ thị được gọi là đồ thị đơn giản / đồ thị nghiêm ngặt nếu đồ thị là vô hướng và không chứa bất kỳ vòng lặp hoặc nhiều cạnh nào.
Đa đồ thị
Nếu trong một đồ thị cho phép có nhiều cạnh giữa cùng một tập các đỉnh thì nó được gọi là Đa đồ thị. Nói cách khác, nó là một đồ thị có ít nhất một vòng lặp hoặc nhiều cạnh.
Đồ thị có hướng và không có hướng
Đồ thị $ G = (V, E) $ được gọi là đồ thị có hướng nếu tập cạnh được tạo thành từ cặp đỉnh có thứ tự và đồ thị được gọi là vô hướng nếu tập cạnh được tạo bởi cặp đỉnh không có thứ tự.
Biểu đồ được kết nối và ngắt kết nối
Một đồ thị được liên thông nếu hai đỉnh bất kỳ của đồ thị được nối với nhau bằng một đường dẫn; trong khi một đồ thị bị ngắt kết nối nếu ít nhất hai đỉnh của đồ thị không được nối với nhau bằng một đường dẫn. Nếu đồ thị G bị ngắt kết nối, thì mọi đồ thị con có liên thông cực đại của $ G $ được gọi là thành phần liên thông của đồ thị $ G $.
Biểu đồ thông thường
Một đồ thị là hình đều nếu tất cả các đỉnh của đồ thị có cùng tung độ. Trong đồ thị thông thường G có tung độ $ r $, tung độ của mỗi đỉnh của $ G $ là r.
Đồ thị hoàn chỉnh
Một đồ thị được gọi là đồ thị hoàn chỉnh nếu mỗi cặp hai đỉnh được nối bởi đúng một cạnh. Đồ thị hoàn chỉnh với n đỉnh được ký hiệu là $ K_n $
Đồ thị chu kỳ
Nếu một đồ thị bao gồm một chu trình đơn, nó được gọi là đồ thị chu trình. Đồ thị chu trình có n đỉnh được ký hiệu là $ C_n $
Đồ thị hai bên
Nếu tập đỉnh của đồ thị G có thể được chia thành hai tập rời rạc, $ V_1 $ và $ V_2 $, theo cách mà mỗi cạnh trong đồ thị nối một đỉnh trong $ V_1 $ với một đỉnh trong $ V_2 $, và không có cạnh nào trong G nối hai đỉnh trong $ V_1 $ hoặc hai đỉnh trong $ V_2 $, khi đó đồ thị $ G $ được gọi là đồ thị hai góc.
Đồ thị lưỡng cực hoàn chỉnh
Một đồ thị lưỡng hợp hoàn chỉnh là một đồ thị hai cực trong đó mỗi đỉnh trong tập thứ nhất được nối với mọi đỉnh đơn trong tập thứ hai. Biểu đồ lưỡng phân hoàn chỉnh được ký hiệu là $ K_ {x, y} $ trong đó biểu đồ $ G $ chứa các đỉnh $ x $ trong tập đầu tiên và $ y $ đỉnh trong tập thứ hai.
Biểu diễn đồ thị
Chủ yếu có hai cách để biểu diễn một biểu đồ -
- Ma trận kề
- Danh sách gần kề
Ma trận kề
Ma trận kề $ A [V] [V] $ là một mảng 2D có kích thước $ V \ times V $ trong đó $ V $ là số đỉnh trong một đồ thị vô hướng. Nếu có một cạnh từ $ V_x $ đến $ V_y $ thì giá trị của $ A [V_x] [V_y] = 1 $ và $ A [V_y] [V_x] = 1 $, nếu không giá trị sẽ bằng không. Và đối với đồ thị có hướng, nếu có một cạnh từ $ V_x $ đến $ V_y $, thì giá trị của $ A [V_x] [V_y] = 1 $, nếu không giá trị sẽ bằng không.
Adjacency Matrix of an Undirected Graph
Chúng ta hãy xem xét đồ thị vô hướng sau đây và xây dựng ma trận kề:
Ma trận kề của đồ thị vô hướng ở trên sẽ là:
a |
b |
c |
d |
|
a |
0 |
1 |
1 |
0 |
b |
1 |
0 |
1 |
0 |
c |
1 |
1 |
0 |
1 |
d |
0 |
0 |
1 |
0 |
Adjacency Matrix of a Directed Graph
Chúng ta hãy xem xét đồ thị có hướng sau và xây dựng ma trận kề của nó:
Ma trận kề của đồ thị có hướng ở trên sẽ là:
a |
b |
c |
d |
|
a |
0 |
1 |
1 |
0 |
b |
0 |
0 |
1 |
0 |
c |
0 |
0 |
0 |
1 |
d |
0 |
0 |
0 |
0 |
Danh sách gần kề
Trong danh sách kề, một mảng $ (A [V]) $ của các danh sách liên kết được sử dụng để biểu diễn đồ thị G với $ V $ số đỉnh. Mục nhập $ A [V_x] $ đại diện cho danh sách được liên kết của các đỉnh liền kề với đỉnh $ Vx-th $. Danh sách kề của biểu đồ vô hướng như trong hình bên dưới -
Đồ thị phẳng so với đồ thị không phẳng
Planar graph- Đồ thị $ G $ được gọi là đồ thị phẳng nếu nó có thể được vẽ trong một mặt phẳng mà không có cạnh nào bị cắt ngang. Nếu chúng ta vẽ đồ thị trong mặt phẳng không có cạnh cắt thì gọi là nhúng đồ thị vào mặt phẳng.
Non-planar graph - Một đồ thị là không phẳng nếu nó không thể được vẽ trong một mặt phẳng không có các cạnh đồ thị cắt nhau.
Isomorphism
Nếu hai đồ thị G và H chứa cùng một số đỉnh nối cùng một phương thì chúng được gọi là đồ thị đẳng phương (kí hiệu là $ G \ cong H $).
Dễ dàng kiểm tra tính không đẳng cấu hơn là đẳng cấu. Nếu điều kiện nào sau đây xảy ra thì hai đồ thị là không đẳng tích -
- Số lượng các thành phần được kết nối là khác nhau
- Các thẻ số do Vertex đặt là khác nhau
- Các thẻ số được thiết lập cạnh khác nhau
- Trình tự cấp độ khác nhau
Thí dụ
Các đồ thị sau là đẳng tích:
Đồng tính
Phép đồng cấu từ đồ thị $ G $ đến đồ thị $ H $ là một ánh xạ (Có thể không phải là một ánh xạ hai chiều) $ h: G \ rightarrow H $ sao cho - $ (x, y) \ in E (G) \ rightarrow (h (x), h (y)) \ in E (H) $. Nó ánh xạ các đỉnh lân cận của đồ thị $ G $ với các đỉnh lân cận của đồ thị $ H $.
Thuộc tính của Homomorphisms
Phép đồng cấu là một phép đẳng cấu nếu nó là một ánh xạ hai mặt.
Phép đồng hình luôn bảo toàn các cạnh và tính liên thông của đồ thị.
Các thành phần của các từ đồng hình cũng là các từ đồng hình.
Để tìm xem có tồn tại bất kỳ đồ thị đồng hình nào của một đồ thị khác hay không là một bài toán không đầy đủ.
Đồ thị Euler
Một đồ thị liên thông $ G $ được gọi là đồ thị Euler, nếu có một đường nhỏ bao gồm mọi cạnh của đồ thị $ G $. Đường dẫn Euler là đường dẫn sử dụng mọi cạnh của đồ thị đúng một lần. Một đường đi Euler bắt đầu và kết thúc ở các đỉnh khác nhau.
Mạch Euler là mạch sử dụng mọi cạnh của đồ thị đúng một lần. Một đoạn mạch Euler luôn bắt đầu và kết thúc ở cùng một đỉnh. Đồ thị liên thông $ G $ là đồ thị Euler nếu và chỉ khi tất cả các đỉnh của $ G $ có bậc chẵn và đồ thị liên thông $ G $ là Eulerian nếu và chỉ khi tập hợp cạnh của nó có thể được phân rã thành các chu trình.
Biểu đồ trên là biểu đồ Euler dưới dạng $ “a \: 1 \: b \: 2 \: c \: 3 \: d \: 4 \: e \: 5 \: c \: 6 \: f \: 7 \: g ”$ bao gồm tất cả các cạnh của biểu đồ.
Đồ thị Hamilton
Một đồ thị liên thông $ G $ được gọi là đồ thị Hamilton nếu có một chu trình bao gồm mọi đỉnh của $ G $ và chu trình được gọi là chu trình Hamilton. Đường đi Hamilton trong đồ thị $ G $ là đường đi bộ đi qua mỗi đỉnh đúng một lần.
Nếu $ G $ là một đồ thị đơn giản có n đỉnh, trong đó $ n \ geq 3 $ Nếu $ deg (v) \ geq \ frac {n} {2} $ cho mỗi đỉnh $ v $, thì đồ thị $ G $ là Đồ thị Hamilton. Đây được gọi làDirac's Theorem.
Nếu $ G $ là một đồ thị đơn giản với $ n $ đỉnh, trong đó $ n \ geq 2 $ nếu $ deg (x) + deg (y) \ geq n $ cho mỗi cặp đỉnh không liền kề x và y, thì đồ thị $ G $ là đồ thị Hamilton. Đây được gọi làOre's theorem.