Cho trước một đồ thị $G =(V;E)$ là một đồ thị đơn. Ta sẽ nêu thêm một số định nghĩa sau
Đồ thị $G'=(V';E')$ là phần bù của G nếu nó là một đồ thị đơn sao cho $V=V'$ và nếu hai cạnh giữa $u;v \in V$ được nối trong G thì không được nối trong G' [và ngược lại]
Gọi ánh xạ $\phi_G$ là ánh xạ nhận diện của đồ thị G đặt tương ứng cạnh của G với hai đầu mút của nó [là một cặp không sắp thứ tự]; .
Đồ thị $G=(V;E)$ và đồ thị $H=(V";E")$ đẳng cấu với nhau nếu tồn tại hai song ánh $\alpha:V\rightarrow V"$ và $\beta: E\rightarrow E"$ thỏa mãn nếu $ \phi_H(e) =uv$ thì $\phi_G(\beta(e)) = \alpha(u)\alpha(v)$
Đồ thị G là tự hoàn chỉnh nếu nó và phần bù của nó đẳng cấu với nhau
a]Chứng minh đồ thị G hoàn chỉnh thì nó có số đỉnh chia hết cho 4 hoặc chia 4 dư 1
b]Chứng minh tồn tại một đỉnh có bậc $2k$ trong một đồ thị hoàn chỉnh có $4k+1$ đỉnh
Bài viết đã được chỉnh sửa nội dung bởi Minhnksc: 18-09-2018 - 21:58
