Cho $G$ là một đồ thị và $x$ là một đỉnh của $G$.Ta xác định một phép biến đổi $\phi_x$ trên $G$ là ta xóa đi tất cả các đoạn có $x$ làm đầu mút và vẽ thêm vào các cạnh $xy$ với $y \in G$ và $y $ không được nối với $x$.Một đồ thị $H$ được gọi là $G-attainable$ nếu tồn tại một dãy các phép biến đổi trên sao cho có thể biến đổi $G$ thành $H$.Cho $ n \in N,4|n $.Chứng minh rằng với mỗi đồ thị $G $với $4n$ đỉnh và $n$ cạnh thì tồn tại một đồ thị $G-attainable$ với ít nhất $\dfrac{9n^2}{4}$ tam giác
Bài 4
Started By tanlsth, 12-07-2008 - 17:03
#1
Posted 12-07-2008 - 17:03
Learn from yesterday,live for today,hope for tomorrow
The important thing is to not stop questioning
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users