Đồ thị (Graph) - Sự kỳ diệu của toán

Dành cho những người hay hỏi: Học toán để làm gì?

Có bài toán “hồi xưa” về 7 cây cầu Königsberg  như sau:

Ở Königsberg (nay là Kaliningrad của Nga) có 7 cây cầu, như hình bên trên. Câu hỏi rằng: Liệu có cách nào đi qua hết 7 cây cầu 1 lần mà không đi lại đường cũ(không đi lại đường đã đi).

Bài toán phát biểu đơn giản chỉ thế thôi. Nhưng đa số chúng ta sẽ xem đây là trò chơi “tìm đường trong mê cung”, rồi ngồi chỉ trỏ, vẽ đường lòng vòng. Một số khác thì xem đây là chuyện “tầm phào” vì không đem lại lợi ích gì nên bỏ qua. Nhưng, hồi năm 1736, Euler ( nhà toán học lỗi lạc người Thụy Sĩ) đã chứng minh được bài toán này bằng 1 cái đồ thị (như phía trên bên phải.).

Đồ thị (Graph) là cách biểu diễn lại thực tế dưới dạng mô hình lý thuyết (model thinking) hoặc trừu tượng hóa đối tượng (Abstract). Làm sao để liệt kê một cách tường minh các tính chất liên quan, quan trọng của vấn đề(Problem), đối tượng(Object) để từ đó tìm ra cách giải.

Môn lý thuyết đồ thị này rất quan trọng với dân toán, mặc dù người “ngoài ngành” nhìn vào chẳng thấy toán chút nào! Dân Tin học cũng được học một chút cái này, đa số như “cưỡi ngựa xem hoa”, không biết học để làm gì!! :D

Thực ra môn này lại là một nền tảng cho Tin học (đây cũng là lý do người ta hay nói muốn học Tin thì phải giỏi Toán và lúc trước có khoa Toán - Tin). Cái gọi là Automata, thiết kế lý thuyết cho một cái máy đơn giản (hay phức tạp, hay bất kỳ) cũng là một cái đồ thị (Graph):

Trạng thái ban đầu |- nhận lệnh a-> (làm gì đó ->  trạng thái 2) |-nhận lệnh b->(làm gì đó, trạng thái 3)|-nhận lệnh c-> (làm gì đó, trở về trạng thái 2)|-.....->....===> là một cái GRAPH!

Trong môi trường văn phòng, chắc ai cũng biết khái niệm quy trình làm việc (Process). Quy trình có thể thay đổi tùy theo từng trường hợp phát sinh và nó cũng dễ dàng biểu diễn bằng đồ thị. Dân lập trình ERP thường đau đầu về quy trình thay đổi, ảnh hưởng nghiêm trọng tới cấu trúc chương trình, nhưng rủi ro này sẽ giảm đi rất nhiều nếu áp dụng Lý Thuyết Đồ Thị ngay từ phân tích ban đầu.

Thực tế, ở những dự án máy móc, kỹ thuật lớn, cao cấp, kiểu thiết kế...máy bay, tàu vũ trụ hay nhà máy sản xuất tự động, siêu chính xác thì Lý thuyết đồ thị được áp dụng trong Formal Design (thiết kế hình thức) để mô phỏng ra các trạng thái, tình huống có thể xảy ra. Rồi từ trên cái đồ thị đó kiếm ra tình huống nào mình không muốn nó xảy ra, để đảm bảo chắc chắn nó không xảy ra. Cũng như đảm bảo cái mình muốn nó xảy ra chắc chắn sẽ xảy ra....

Đồ thị còn được áp dụng trong việc gì nữa nhỉ? A, toàn những từ “đao to, búa lớn” như Data Mining, Machine Learning, AI (Artificial Intelligence), Deep Learning..(hình bên phải , phía dưới). Muốn làm mấy cái “to lớn” kia, trước tiên dân Tin học phải học cách cài đặt (Implement) một cái Graph là thế nào trước đã! Không làm được thì miễn nói chuyện tiếp nhá!

Khái niệm Neural Network lấy ý tưởng từ cách hoạt động của các nơ rôn thần kinh não người. Nó cũng là một cái đồ thị. Mà đến tận bây giờ, người nghĩ bản chất của khả năng tư duy, suy nghĩ, giải quyết vấn đề của con người cũng...là một cái đồ thị! Trí tuệ con người hay trí tuệ nhân tạo cũng là đồ thị!

Tóm lại, bạn vẫn nghĩ toán chỉ là để cộng trừ nhân chia thôi sao? Nghĩ lại đi nhé!

(Của người bạn)