Ảnh hưởng của tính chất đồ thị lên ràng buộc giữa các bất biến trong cây và đồ thị phẳng
Influences of graph’s quality on the invariables’ relationship in tree and plane graph
Khổng Chí Nguyện , Vũ Thị Khánh Trình, Nguyễn Văn Dân
Tóm tắt
Lý thuyết đồ thị là một ngành Toán học có nhiều ứng dụng quan trọng trong Tin học và trong thực tế. Những ý t­ưởng cơ bản được đ­ề ra bởi nhà toán học Thuỵ sĩ Leonhar Euler (1707-1783). Ông đã dùng đồ thị để giải quyết bài toán nổi tiếng về 7 chiếc cầu ở Konigsberg. Bằng mô hình đồ thị, chúng ta có thể giải quyết được nhiều bài toán thực tế như: tìm cách để tham quan một triển lãm sao cho mỗi một hành lang đi qua đúng một lần, tìm số mầu ít nhất để tô mầu bản đồ, biểu diễn sự ảnh hưởng lẫn nhau giữa các cá nhân trong một tổ chức hay sự cạnh tranh giữa các loài trong môi tr­ường tự nhiên... Giữa tính chất của đồ thị và các bất biến trong đồ thị có mối liên hệ ràng buộc chặt chẽ với nhau. Bài báo này chỉ trình bày một số kết quả về ảnh hưởng của tính chất của đồ thị lên ràng buộc giữa các bất biến trong cây và đồ thị phẳng.
Từ khóa: đồ thị; cây; đồ thị phẳng; cạnh; đỉnh.
ABSTRACT
Graph Theory is a Mathematic field which has many important applications in Informatics and in reality. The basic ideas were proposed by the Swiss Mathematician - Leonhar Euler (1707-1783). He used graphs to solve the famous problem of 7 brigdes in Konigsberg. By using graph models, we can solve many factual problems such as looking for a way to visit an exhibition so that each corridor is passed only once, finding the fewest numbers of colours to colour a map, showing an mutual effects among individuals in a group or a competition among species in natural environment… There is a close relationship between graph’s features and the invariables in graph. This paper only presents some results of the effects of the former on the relationship among the latter in tree and plane graphs.
Keyword: graph; tree; plane graph; vertex; edge.