Lý thuyết đồ thị - Ví dụ
Trong chương này, chúng tôi sẽ trình bày một vài ví dụ tiêu chuẩn để chứng minh các khái niệm mà chúng ta đã thảo luận trong các chương trước.
ví dụ 1
Find the number of spanning trees in the following graph.
Giải pháp
Số cây khung thu được từ đồ thị trên là 3. Chúng như sau:
Ba cây này là cây bao trùm cho các đồ thị đã cho. Ở đây đồ thị I và II là đẳng tích của nhau. Rõ ràng, số cây khung không đẳng cấu là hai.
Ví dụ 2
How many simple non-isomorphic graphs are possible with 3 vertices?
Giải pháp
Có thể có 4 đồ thị không đẳng phương có 3 đỉnh. Chúng được hiển thị bên dưới.
Ví dụ 3
Let ‘G’ be a connected planar graph with 20 vertices and the degree of each vertex is 3. Find the number of regions in the graph.
Giải pháp
Theo định lý tổng độ,
20 Σ i = 1 deg (Vi) = 2 | E |
20 (3) = 2 | E |
| E | = 30
Theo công thức của Euler,
| V | + | R | = | E | + 2
20+ | R | = 30 + 2
| R | = 12
Do đó, số vùng là 12.
Ví dụ 4
What is the chromatic number of complete graph Kn?
Giải pháp
Trong một đồ thị hoàn chỉnh, mỗi đỉnh kề với còn lại (n – 1) đỉnh. Do đó, mỗi đỉnh yêu cầu một màu mới. Do đó số sắc K n = n.
Ví dụ 5
What is the matching number for the following graph?
Giải pháp
Số đỉnh = 9
Chúng ta chỉ có thể ghép 8 đỉnh.
Số phù hợp là 4.
Ví dụ 6
What is the line covering number of for the following graph?
Giải pháp
Số đỉnh = | V | = n = 7
Số phủ dòng = (α 1 ) ≥ [n / 2] = 3
α 1 ≥ 3
Bằng cách sử dụng 3 cạnh, chúng ta có thể bao gồm tất cả các đỉnh.
Do đó, số lượng dòng bao phủ là 3.