Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh

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


  • Please log in to reply
Chưa có bài trả lời

#1 Minhnksc

Minhnksc

    Sĩ quan

  • Thành viên
  • 301 Bài viết
  • Giới tính:Nam
  • Đến từ:Các bạn biết là từ đâu rồi đấy :D
  • Sở thích:vinahey :V

Đã gửi 13-08-2018 - 23:57

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

:D :D :D
“Nhà khoa học không nghiên cứu tự nhiên vì việc đó có ích; Anh ta nghiên cứu nó vì anh ta thấy thích thú và anh ta thấy thích thú vì nó đẹp. Nếu tự nhiên không đẹp thì nó không đáng để biết, và cuộc sống không đáng để sống” :D :D :D




0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh