Cổng Thông Tin Đại Học, Cao Đẳng Lớn Nhất Việt Nam

Lý thuyết đồ thị là gì? Xem xong 5 phút hiểu luôn.

KHOA Y DƯỢC HÀ NỘI

Thẳng tiến vào đại học chỉ với: Điểm lớp 12 Từ 6,5 Điểm thi từ 18 năm 2021

Lý thuyết  Đồ thị, trong toán học rời rạc,  là nghiên cứu về đồ thị. Đồ thị được xác định là một cấu trúc toán học biểu diễn một hàm cụ thể bằng cách nối một tập hợp các điểm. Nó được sử dụng để tạo mối quan hệ theo cặp giữa các đối tượng.Đồ thị được tạo thành từ các đỉnh (nút) được nối với nhau bởi các cạnh (đường). Các ứng dụng của biểu đồ tuyến tính không chỉ được sử dụng trong Toán học mà còn được sử dụng trong các lĩnh vực khác như Khoa học máy tính, Vật lý và Hóa học, Ngôn ngữ học, Sinh học, … Trong thực tế, ví dụ tốt nhất về cấu trúc đồ thị là GPS, nơi bạn có thể theo dõi con đường hoặc biết hướng của con đường.

Đồ thị là gì

Trong Toán học, biểu đồ là một biểu diễn bằng hình ảnh của bất kỳ dữ liệu nào một cách có tổ chức. Biểu đồ thể hiện mối quan hệ giữa các đại lượng biến thiên. Trong lý thuyết đồ thị, đồ thị đại diện cho một tập hợp các đối tượng, có liên quan với nhau theo một nghĩa nào đó. Các đối tượng về cơ bản là các khái niệm toán học, được biểu thị bằng các đỉnh hoặc các nút và mối quan hệ giữa các cặp nút, được biểu thị bằng các cạnh.

Lịch sử

Lịch sử của lý thuyết đồ thị cho biết nó được đưa ra bởi nhà toán học Thụy Sĩ nổi tiếng tên là Leonhard Euler , để giải quyết nhiều vấn đề toán học bằng cách xây dựng đồ thị dựa trên dữ liệu cho trước hoặc một tập hợp các điểm. Biểu diễn đồ họa cho thấy các loại dữ liệu khác nhau dưới dạng biểu đồ thanh, bảng tần số, biểu đồ đường, biểu đồ hình tròn, biểu đồ đường, v.v.

Định nghĩa

Lý thuyết đồ thị là nghiên cứu về điểm và đường. Trong Toán học, nó là một lĩnh vực phụ liên quan đến việc nghiên cứu các đồ thị. Nó là một biểu diễn bằng hình ảnh đại diện cho sự thật Toán học. Lý thuyết đồ thị là nghiên cứu về mối quan hệ giữa các đỉnh (nút) và các cạnh (đường).

Về mặt hình thức, một đồ thị được biểu thị là một cặp G (V, E).

Trong đó V đại diện cho các đỉnh của tập hữu hạn và E đại diện cho các cạnh của tập hữu hạn.

Do đó, chúng ta có thể nói một đồ thị bao gồm tập các đỉnh V và tập các cạnh E. không rỗng.

Thí dụ

Giả sử, một Đồ thị G = (V, E), trong đó

Các đỉnh, V = {a, b, c, d}

Các cạnh, E = {{a, b}, {a, c}, {b, c}, {c, d}}

Các loại đồ thị

Các biểu đồ về cơ bản có hai loại, có hướng và không có hướng. Nó được hiểu rõ nhất bằng hình dưới đây. Mũi tên trong hình chỉ hướng.

Lý thuyết đồ thị

Đồ thị hướng

Trong lý thuyết đồ thị, đồ thị có hướng là đồ thị được tạo thành từ một tập hợp các đỉnh được nối với nhau bởi các cạnh, trong đó các cạnh có hướng liên kết với chúng.

Đồ thị vô hướng

Đồ thị vô hướng được định nghĩa là đồ thị trong đó tập hợp các nút được kết nối với nhau, trong đó tất cả các cạnh đều có hướng. Đôi khi, loại đồ thị này được gọi là mạng vô hướng.

Các loại đồ thị khác

  • Null Graph: Một đồ thị không có cạnh.
  • Đồ thị đơn giản: Đồ thị vô hướng và không có bất kỳ vòng lặp hoặc nhiều cạnh nào.
  • Đa đồ thị: Một đồ thị có nhiều cạnh giữa cùng một tập các đỉnh. Nó có các vòng lặp được hình thành.
  • Đồ thị được kết nối: Một đồ thị trong đó hai đỉnh bất kỳ được nối với nhau bằng một đường dẫn.
  • Đồ thị ngắt kết nối: Một đồ thị trong đó hai đỉnh hoặc nút bất kỳ bị ngắt kết nối bởi một đường dẫn.
  • Đồ thị chu kỳ: Một đồ thị hoàn thành một chu trình.
  • Đồ thị hoàn chỉnh: Khi mỗi cặp đỉnh được nối với nhau bằng một cạnh thì đồ thị đó được gọi là đồ thị hoàn chỉnh
  • Đồ thị phẳng: Khi không có hai cạnh nào của đồ thị cắt nhau và tất cả các đỉnh và cạnh đều được vẽ trong một mặt phẳng, thì đồ thị như vậy được gọi là đồ thị phẳng

Thuộc tính của đồ thị

  • Điểm bắt đầu của mạng được gọi là gốc.
  • Khi các loại nút giống nhau được kết nối với nhau, khi đó đồ thị được gọi là đồ thị phân loại, nếu không nó được gọi là đồ thị phân loại.
  • Đồ thị chu trình được cho là đồ thị có một chu trình duy nhất.
  • Khi tất cả các cặp nút được nối với nhau bằng một cạnh duy nhất, nó sẽ tạo thành một đồ thị hoàn chỉnh.
  • Một đồ thị được cho là đối xứng khi mỗi cặp đỉnh hoặc nút được kết nối theo cùng một hướng hoặc theo hướng ngược lại.
  • Khi một đồ thị có một đồ thị duy nhất, nó là một đồ thị đường dẫn.

Cây, mức độ và chu kỳ của đồ thị

Có một số thuật ngữ nhất định được sử dụng trong biểu diễn đồ thị như Độ, Cây, Chu kỳ, v.v. Hãy cùng chúng tôi tìm hiểu sơ lược về chúng.

Cây:  Cây trong biểu đồ là kết nối giữa các mạng vô hướng chỉ có một đường dẫn giữa hai đỉnh bất kỳ. Nó được giới thiệu bởi nhà toán học người Anh Arthur Cayley vào năm 1857. Cây đồ thị chỉ có các đường thẳng giữa các nút theo bất kỳ hướng cụ thể nào nhưng không có bất kỳ chu trình hoặc vòng lặp nào. Do đó cây cối là đồ thị có hướng.

Mức độ:  Một mức độ trong một đồ thị được đề cập là số cạnh được kết nối với một đỉnh. Nó được ký hiệu là deg (v), trong đó v là một đỉnh của đồ thị. Vì vậy, về cơ bản nó là số đo của đỉnh.

Chu trình:  Chu trình là một đường khép kín trong đồ thị tạo thành một vòng lặp. Khi điểm bắt đầu và điểm kết thúc giống nhau trong một đồ thị có chứa một tập các đỉnh, thì chu trình của đồ thị được hình thành. Khi không có sự lặp lại của đỉnh trong một mạch kín, thì chu trình là một chu trình đơn giản. Đồ thị chu trình được kí hiệu là C n .

  • Một chu trình có số cạnh hoặc số đỉnh là số chẵn được gọi là chu trình chẵn.
  • Chu trình có số cạnh hoặc đỉnh là số lẻ được gọi là Chu trình lẻ.

Thuật toán lý thuyết đồ thị

Thủ tục để vẽ một đồ thị cho bất kỳ hàm nào đã cho hoặc để tính một hàm bất kỳ là thuật toán của đồ thị. Về cơ bản, có các bước hoặc tập hợp hướng dẫn được xác định trước phải được tuân theo để giải quyết một vấn đề bằng phương pháp đồ họa. Có nhiều loại thuật toán khác nhau mà lý thuyết đồ thị tuân theo, chẳng hạn như;

  • Thuật toán Bellman-Ford
  • Thuật toán của Borůvka
  • Thuật toán Ford – Fulkerson
  • Thuật toán Edmonds – Karp và nhiều thuật toán khác.

Tải xuống Ứng dụng học tập của BYJU và học cách biểu diễn các phương trình toán học dưới dạng đồ thị.

Câu hỏi thường gặp – Câu hỏi thường gặp

Lý thuyết đồ thị là gì?

Lý thuyết đồ thị là một nghiên cứu về đồ thị trong toán học rời rạc. Các đồ thị ở đây được biểu diễn bởi các đỉnh (V) và các cạnh (E). Một đồ thị ở đây được ký hiệu là G (V, E).

Đồ thị hữu hạn là gì?

Một đồ thị có số đỉnh và số cạnh hữu hạn được gọi là đồ thị hữu hạn.

Đồ thị rỗng có bao nhiêu cạnh?

Một đồ thị rỗng không có cạnh.

Nếu tung độ của đỉnh là 2 thì nó là đỉnh gì?

Nếu tung độ của đỉnh là 2 thì nó là đỉnh chẵn.

Một đồ thị đơn giản là có hướng hay vô hướng?

Một đồ thị đơn giản là vô hướng và không có nhiều cạnh.

Nếu hai cạnh của một đồ thị được nối với nhau bởi một đỉnh duy nhất, chúng được gọi là các cạnh kề nhau. Đúng hay sai?

0 0 votes
Article Rating
Theo dõi
Thông báo của
guest
0 Comments
Inline Feedbacks
View all comments

Khoa Y Dược Hà Nội tuyển sinh chính quy

Bài viết mới nhất

Thi trắc nghiệm online
https://tintuctuyensinh.vn/wp-content/uploads/2021/10/Autumn-Sale-Facebook-Event-Cover-Template-1.gif
0
Would love your thoughts, please comment.x
()
x