Hướng dẫn giải bài tập lý thuyết đồ thị

#1

Cho đồ thị vô hướng G = <V, E> có |E| = |V| - 1. G không có đỉnh cô lập.

Chứng minh rằng, G có ít nhất 1 đỉnh bậc 1.
Chứng minh rằng, G có ít nhất 2 đỉnh bậc 1.

Theo phân tích bài thì G là đồ thị đơn vô hướng vì số cung nhỏ hơn số đỉnh - 1, nhưng mình không biết làm sao để chứng minh, mình chẳng có ý tưởng mình dốt đặc máy vụ chứng mình này

#2

Hi Vĩ Huỳnh.

  1. Sao lại :
    “Chứng minh rằng, G có ít nhất 1 đỉnh bậc 1.
    Chứng minh rằng, G có ít nhất 2 đỉnh bậc 1.”
  2. Bạn thử dùng phản chứng xem. Khi không có đỉnh nào bặc 1 -> v.v.v…
#3

Ok thank bạn để mình thử, đây là bài tập trong slide bài giảng của Thầy mình mà nghĩ mãi ko ra

#4

Dirichlet :smiley: sử dụng tối đa cái giả thiết đỉnh cô lập nhé :slight_smile:

2 Likes
#5

làm sao biết bó có đỉnh bậc 1 , biết nó có đỉnh bậc 1 mới sử dụng được dirichlet chứ bạn

#6

Không có đỉnh cô lập <-> đỉnh nào cũng nối được với ít nhất 1 đỉnh khác <-> bậc >= 1.

1 Like
#7

mình cũng từng nghĩ như bạn, nhưng nếu vậy thì quá đơn giản rùi phải ko cậu

#8

Nếu |E| = |V| - 1, G không có điểm cô lập, suy ra G là tree.

Vì G là tree nên tồn tại g thuộc G là leaf node, leaf node có bậc là 1, câu 1 được chứng minh.

Câu 2 xét 2 trường hợp:

  • Bậc của root node là bằng 1, G là tree => tồn tại leaf node có bậc là 1. Root node và leaf node là 2 node cần tìm => G có ít nhất 2 node bậc 1.
  • Bậc của root node > 1, G có ít nhất 2 sub trees. Mỗi sub tree có ít nhất 1 leaf node bậc 1 => G có ít nhất 2 node bậc 1.

Chém vậy thôi, chứ mình chả biết đúng hay không đâu :joy:

3 Likes
#9

bạn có ý tưởng nào về cách sử dụng công thức đề bài cho để chứng minh ra kết quả không

#10

để ý là tổng số bậc của các đỉnh của 1 đồ thị luôn luôn bằng 2 lần số cạnh. Vì khi thêm 1 cạnh vào 1 đồ thị, bậc của 2 đỉnh của cạnh đó sẽ tăng lên 1 đơn vị nên tổng số bậc của các đỉnh tăng lên 2.

giả sử G ko có đỉnh bậc 1. Vì G ko có đỉnh cô lập, suy ra bậc của mỗi đỉnh trong G lúc này đều >= 2. Vậy tổng số bậc của các đỉnh >= 2*|V|. Vậy số cạnh >= |V|, ko đúng vì số cạnh đề cho là |E| = |V| - 1 < |V|. Vậy G phải có ít nhất 1 đỉnh bậc 1.

G có |V| - 1 cạnh nên tổn số bậc của các đỉnh là 2*|V| - 2. Vì G ko có đỉnh cô lập nên số bậc của mỗi đỉnh ít nhất là 1. Lấy |V| bậc từ 2*|V| - 2 để chia cho từng đỉnh, bảo đảm G ko có đỉnh cô lập, còn lại |V| - 2 bậc. Để chia |V| - 2 bậc cho |V| đỉnh thì ít nhất phải có 2 đỉnh ko được chia, hay có ít nhất 2 đỉnh bậc 1.

4 Likes
#11

Hi tntxtnt.
Không nhầm thì có quy định là không giải hộ bài tập thì phải @_@!

#12

hình như là ko nên hỏi bài tập chứ ko có cấm giải bài tập :V

1 Like
#13

mình chỉ hỏi ý tưởng bạn ơi,

#14

cảm ơn bạn rất nhiều vì đã giải luôn

#15

đau lòng quá đáng lẽ gợi ý tổng số bậc = 2 lần số cạnh là đc rồi

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?