Bài tập Toán rời rạc : Đồ thị

Ậ

Ờ Ạ

BÀI T P TOÁN R I R C ***

CH

: NG 2

ƯƠ

Đ THỒ Ị Đ THỒ Ị

ả

: Nguy n M u Hân ễ ậ ị ệ ệ : Nguy n Th Di u ễ ự

Gi ng viên Sinh viên th c hi n H ngằ L pớ : Tin K30D

* Bài 1:

ạ ậ ớ ng ng là b c l n

Cho G là m t đ th có v đ nh và e c nh.M và m t ỉ nh t và nh nh t c a các đ nh c a G.Ch ng minh r ng: ỉ ộ ồ ị ấ ủ ươ ứ ằ ấ ỏ

ủ ứ 2.e/v £ m £ M

i: L i gi ờ ả

ỏ ủ ủ ấ ủ ỉ ấ ủ ỉ

ư ậ

i) : b c c a đ nh v i) ậ ủ ỉ

(v i deg(v ớ

Theo đ ra ta có: ề M: b c l n nh t c a đ nh c a G. ậ ớ m: b c nh nh t c a đ nh c a G. ậ Nh v y: m £ v.m £ v.m £ m £ V y ta có đi u ph i ch ng minh. ậ deg(vi) £ ∑deg(vi) £ 2.e £ 2.e £ ả ề M v.M v.M M ứ

* Bài 2:

đ nh và e c nh, khi ứ ồ ị ế ằ ơ ỉ ạ

Ch ng minh r ng n u G là đ n đ th phân đôi có v đó

e £ L i gi ờ v2/4. ả : i

1 và V2.

Ta có: G=(V,E) là đ n đ th phân đôi. ồ ị V=V1 U V2, V1 ∩ V2 =ø, V1 ≠ ø, V2 ≠ ø. c a V t là s ph n t ầ ử ủ ầ ượ ố G i nọ 1 và n2 l n l

ồ ị ồ ị n1 + n2 = v ị ạ

G là đ th phân đôi nên e đ t giá tr max khi G là đ th phân đôi đ y đ .Khi đó: ầ ủ

Có nghĩa là trong tr ườ

£ ng h p t ng quát thì: n1.n2 v2/4 ch c n ch ng minh: e = n1.n2 ợ ổ e £ Nh v y, đ ch ng minh e ể ứ ư ậ ỉ ầ ứ

n1.n2£ v2/4

Th t v y: ậ ậ n1.n2 £ v2/4

2 + 2.n1.n2

n1.n2 £ 4.n1.n2 £ 2 + n2 n1 (n1- n2)2 (n1+ n2)2/4 2 + n2 n1 2 - 2.n1.n2 ≥ 0£ v2/4 ≥ 0 (hi n nhiên đúng) ể

Suy ra: e £

V y ta có đi u ph i ch ng minh. n1.n2 £ ề v2/4 ả ứ ậ

i k t n i n=m ộ ử

ươ ượ ể ướ ế ố ộ ử

2 b x lý song song, – 1) mod m, j), P(i, (j– 1) ẽ ủ ướ

i. Hãy v ạ

* Bài 3: Trong m t ph ộ b x lý P(i,j) đ ộ ử mod m), sao cho các k t n i bao xung quanh các c nh c a l m ng ki u l ng án này. ể ướ ạ

ng án m ng ki u l ạ c k t n i v i 4 b x lý (P(i ế ố ớ ế ố i có 16 b x lý theo ph ộ ử L i gi ờ ươ ả : i

P(0,0) P(0,1)

P(2,0) P(2,1)

P(0,3) P(0,2)

P(2,3) P(2,2)

P(3,0) P(3,1)

P(1,0) P(1,1)

P(3,3) P(3,2)

P(1,3) P(1,2)

* Bài 4:

ng đ c bi u di n b i ma tr n li n k sau: ồ ị ướ ượ ề ề ễ ậ ở

Hãy v các đ th vô h ẽ a) ể b)

1 2

2 0 3 3 4 4 1

1 2 0 1 2 0 0 0 0 3 3 1 1 0 1 0

0 3 0 0 2 4 0 1 2 3 3 1 1 0 1 0 1 3 0 4

i: 1 2 1 3 0 L i gi ờ ả

a) b) V V

2

1

V V V V

2

3

4

V c)

1

V V

2

5

V V

4

3

*Bài 5:

ủ ổ trên m t hàng (t ộ ươ ộ

ầ ử ộ ồ ị ề ậ ủ ng ng c t) c a ứ ng ? Đ i v i đ th có ố ớ ồ ị ướ

ng ? Nêu ý nghĩa c a t ng các ph n t m t ma tr n li n k đ i v i m t đ th vô h ề ố ớ ộ h ướ

L i gi i: ờ ả 1,v2,...,vn }

ồ ị ề ậ ậ

Cho đ th G=(V,E).V= {v Ma tr n li n k c a đ th G=(V,E) là ma tr n: ề ủ ồ ị A=( aij ) v i 1≤i,j≤n ớ a11 a12 ... a1n a21 a22 ... a2n

A= .........

an1 an2 ... ann

: ế

*N u G là đ th vô h ngướ ồ ị aij là s c nh n i đ nh v i và vj ố ỉ ố ạ -T ng hàng i c a ma tr n A: ậ ủ ổ

n ∑ aij chính là b cậ c a đ nh v i j=1

ủ ỉ

-T ng c t j c a ma tr n A: ủ ậ ổ ộ

ủ ỉ n ∑aij chính là b cậ c a đ nh v j i=1

ế

ỉ

: ngướ *N u G là đ th có h ồ ị j mà vj là đ nh cu i aij là s cung n i vi và v ố ố ố -T ng hàng i c a ma tr n A: ậ ủ ổ

n ∑ aij chính là b c raậ j=1

c a đ nh v i ủ ỉ

-T ng c t j c a ma tr n A: ủ ậ ộ ổ

c a đ nh v j ủ ỉ n ∑aij chính là b c raậ i=1

*Bài 6: ậ ề

Tìm ma tr n li n k cho các ma tr n sau: ề b) Cn ậ c) Wn a) Kn d) Km,n e) Qn

i: ờ ả

a) Ma tr n li n k c a đ th đ y đ K ... L i gi ề ủ ồ ị ầ ủ n: ai2 ... ậ ề ai1 aij ain

a1j a2j ... aij ... anj 0 1 ... 1 ... 1 1 1 ... 1 0 ... ... ... ... 1 ... 0 ... ... ... 1 1 ... ... 1 ... 1 ... ... ... 1 ... ... ... 0

Hay vi ế

Ma tr n li n k c a đ th đ y đ K t cách khác: ề ậ ề ủ ồ ị ầ ủ n là:

n u i = j ế

0 A = (aij), trong đó aij = 1 n u i ≠ j ế

b) Ma tr n li n k c a đ th vòng C ề ủ ồ ị ề ậ

ai1 ai2 ai3 aij-1 aij+1 ain-1 ain ... aij ...

... ... ... ... ... ... ... 0 1 0 ... 0 ... 0 0 0 0 ... 0 ... 0 0 0 0 ... 1 ... 0 ... ... ... ... ... ... ... 0 0 0 ... 0 ... 1 1 0 0 ... 0 ... 0 0 1 0 ... 0 ... 1 a1j a2j a3j ... aij ... anj 1 0 1 ... 0 ... 0 0 0 0 ... 1 ... 0

Vi t cách khác: ế

n là:

Ma tr n li n k c a đ th vòng C ề ủ ồ ị ề

ậ A = (aij), trong đó:

ij=

1 n u j=2 ho c j=n ế ặ

- V i i=1: a ớ

0 n u j≠2và j≠n ế

1 n u j=1 ho c j=n-1 ế ặ

aij= - V i i=n: ớ

0 n u j≠1 và j≠n-1 ế

-V i i≠1 và i≠n: ớ

1 n u j=i+1, j=i-1 ế

aij = 0 n u j≠i+1 và j≠i-1 ế

c) Ma tr n li n k A c a đ th bánh xe W ủ ồ ị ề ề ậ

ai1 ai2 ai3 aij-1 aij+1 ain-1 ain ain +1 ... ... aij

a1j a2j ... aij ... anj an+1j 0 1 ... 0 ... 1 1 1 0 ... 0 ... 0 1 ... ... ... ... ... ... ... 0 1 ... 0 ... 0 1 0 0 ... 1 ... 0 1 1 1 ... 1 ... 1 0 ... ... ... ... ... ... ... 0 0 ... 0 ... 1 1 0 0 ... 1 ... 0 1 1 0 ... 0 ... 0 1 0 0 ... 0 ... 0 1

d) Ma tr n li n k c a đ th phân đôi đ y đ K ề ủ ồ ị ầ ủ m,n: ề ậ

Cho G=(V,E)=Km,n, trong đó V=V1 U V2

V1={v1,v2,...,vm} V2={v'1,v'2,...,v'n}

ề ủ ề ậ

m,n nh sau: ư v'1

Ta có ma tr n li n k c a K v1 v2 ... vm v'2 ... v'n

v1 v2 ... vm v'1 v'2 ... v'n 0 0 ... 0 1 1 ... 1 0 0 ... 0 1 1 ... 1 ... ... ... ... ... ... ... ... 1 1 ... 1 0 0 ... 0 ... ... ... ... ... ... ... ... 1 1 ... 1 0 0 ... 0 1 1 ... 1 0 0 ... 0 0 0 ... 0 1 1 ... 1

n( 2n đ nh ng v i n xâu

ng Q ậ ề ươ ỉ ứ ớ

ề ủ ồ ị ậ ứ

e) Ma tr n li n k c a đ th l p ph nh phân khác nhau ch a bit 0, 1) ị 00..00 00..01 00..10 00..11 ... 10..00 10..01 ... 11..11

0 0 1 ... 1 ... 0

1 1 0 ... 1 0 ... 0 0 1 ... 0 0 0 ... 0 0 1 1 0 ... 0 0 ... 0

0 00..00 1 00..01 00..10 1 00..11 0 ... ... 10..00 1 0 0 0 ... 0 1 ... 0 10..01 0 0 0 0 ... 1 0 ... 0 ... 11..11 0 0 0 0 ... 0 0 ... 0

*Bài 7: Hai đ n đ th v i ma tr n li n k sau đây có là đ ng c u không? ề ơ ồ ị ớ ề ẳ ậ ấ

Ma tr n 1ậ

Ma tr n 2ậ

0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0

L i gi i: ờ ả

c 2 đ th t • Cách 1: D a vào ma tr n li n k , ta có th v đ ề ự ể ẽ ượ ề ậ ồ ị ươ ứ ng ng

nh sau: ư

V1 V2

V' 1 V' 2

V3 V4

V' 4 V' 3 G1 G2

ớ ớ ậ ậ

G1=(V,E): đ th ng v i ma tr n 1 ồ ị ứ G2=(V',E'): đ th ng v i ma tr n 2 ồ ị ứ D dàng nh n th y: ấ ậ

ồ ị ủ ạ ạ

ễ - S c nh c a 2 đ th khác nhau: G1 có 4 c nh, G2 có 5 c nh ố ạ - Ngoài ra:

ỉ ỉ ỉ

ậ

ỉ ỉ

V y 2 đ th trên không đ ng c u. G1 có 1 đ nh b c 1 (V3) ậ 2 đ nh b c 2 (V1,V2) ậ 1 đ nh b c 3 (V4) ậ G2 không có đ nh b c 1 ỉ 2 đ nh b c 2(V'2,V'3) ậ 2 đ nh b c 3(V'1,V'4) ậ ấ ồ ị ẳ ậ

• Cách 2: T ng các ph n t ầ ử ồ ị ằ

ậ ề ầ ố ạ

ậ ậ

trong ma tr n li n k c a đ n đ th b ng t ng ổ ề ủ ơ ổ s b c c a các đ nh và b ng 2 l n s c nh c a đ th . ủ ồ ị ằ ố ậ ủ ừ - Đ th ng v i ma tr n 1 có 8:2=4 c nh - Đ th ng v i ma tr n 2 có 10:2=5 c nh ư ậ ỉ T 2 ma tr n trên ta có: ậ ồ ị ứ ồ ị ứ ơ ớ ớ ồ ị ứ ạ ạ ề ề ậ ớ

Nh v y, 2 đ n đ th ng v i 2 ma tr n li n k trên không đ ng ẳ c u.ấ

*Bài 8: Hai đ n đ th v i ma tr n liên thu c sau có là đ ng c u không? ơ ồ ị ớ ậ ẳ ấ ộ

1 1 0 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1

i: L i gi ờ ả

ậ

- Ma tr n 1: e2 e1 e3 e4 e5

ng v i đ th G=(U,E) ứ ớ ồ ị

1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 1 0

u1 u2 u3 u4

ậ

- Ma tr n 2: e'2 e'1 e'3 e'4 e'5

ng v i đ th G'=(V,E') ứ ớ ồ ị

0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1 v1 v2 v3 v4

e1 e'2 U 1 U 2 V 1 V 2

e2 e3 e5 e'5 e'3 e'4

U 4 U 3 V 4 V 3 e4 e'1

G'=(V,E')

ấ

G=(U,E) Xét phép đ ng c u f: ẳ e1→e'2 e2→e'5 e3→e'3 e4→e'1 e5→e'4

Lúc này, ta bi u di n l i ma tr n liên thu c c a đ th G' theo th ể ộ ủ ồ ị ứ

ễ ạ 1, v2, v3,v4 và th t t các đ nh v ỉ ứ ự ự ư

2, e'5, e'3, e'1, e'4 nh sau: e'4

e'2 e'5 ậ các c nh e' ạ e'1 e'3

v1 v2 v3 1 1 0 1 0 0 0 1 0 0 1 1 0 0 1

v4 0 1 1 1 0

ậ ộ ủ ậ ằ

Ma tr n n ày và ma tr n liên thu c c a G b ng nhau. V y G và G' đ ng c u v i nhau. ẳ ấ ậ ớ

* Bài 9: Các đ th G và G’ sau có đ ng c u v i nhau không? ồ ị ẳ ấ ớ

L i gi i: ờ ả

a) Xét phép đ ng c u f: ẳ ấ

u1→v2 u2→v3 u3→v6 u4→v5 u5→v4 u6→v1

6, u1, u2, u5, u4,

các đ nh u ỉ

ậ ề ậ ề ủ ề ủ ằ Lúc này, ma tr n li n k c a G (theo th t ứ ự ằ

ề u3) và ma tr n li n k c a G' là b ng nhau và b ng: 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1

V y G và G’ đ ng c u v i nhau. ẳ ậ ấ ớ

3, v4, v1, v5, v2,

ẳ

các đ nh v ỉ b)Xét phép đ ng c u f: ấ u1→v3 u2→v5 u3→v1 u4→v2 u5→v4 u6→v6 ề

ậ ề

Lúc này, ma tr n li n k c a G(theo th t ứ ứ v6) và na tr n li n k c a G’ b ng nhau và b ng: ằ 0 1 1 0 0 1 0 0 0 0 1 0 ậ ề ủ 0 0 0 1 0 0 ề ủ ằ 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0

V y, hai đ th G và G’ đ ng c u v i nhau. ồ ị ấ ẳ ớ

ậ * Bài 10:

Cho V={2,3,4,5,6,7,8} và E là t p h p các c p ph n t ậ ủ

(u,v) c a V ng G=(V,E). ầ ử ướ

đ nh 2 t ặ ẽ ồ ị ớ ỉ

ừ ỉ i: ợ sao cho u

ặ ầ ử ề ầ ỏ

(u,v) th a mãn yêu c u đ bài là: Các c p ph n t E={(2,3), (2,5), (2,7), (3,4), (3,5), (3,7), (3,8), (4,5), (4,7), (5,6), (5,7),

Đ th G c n v : (5,8), (6,7), (7,8)} ầ ồ ị ẽ

2 3 4 12

5 6 7 8

Các đ t đ dài 3 đi t 2 đ n 8 là: ườ ệ ộ ừ ế

ng đi phân bi 2, 3, 7, 8 2, 3, 5, 8 2, 5, 7, 8

* Bài 11: Hãy tìm s đ ng đi đ dài n gi a hai đ nh li n k (t. ề ư ữ ề ỉ ề . không li n

ỗ

k ) tùy ý trong K ề a) n=2 ộ ố ườ 3,3 v i m i giá tr c a n sau: ớ b) n=3 ị ủ c) n=4 d) n=5

L i gi i: ờ ả

V V V

5 4 K3,3 * Cách 1: ậ

c chia làm 2 ph n: ầ ủ

ầ ầ

3,3 đ ượ 1, V2, V3 4, V5, V6 ộ ộ

ề ầ

ầ

G i d là s đ T p các đ nh c a K ỉ - Ph n 1 g m V ồ - Ph n 2 g m V ồ Trong đó, 2 đ nh thu c cùng 1 ph n thì không li n k ề ỉ 2 đ nh thu c 2 ph n khác nhau thì li n k . ề ỉ 3,3. ố ườ ng đi đ dài n gi a 2 đ nh thu c K ữ ề ộ ọ ộ ỉ

* N u ế n ch nẵ thì đi m đ u và đi m cu i c a đ ố ủ ườ ể ả ằ ng đi ph i n m

ể trong cùng 1 ph n (chúng không li n k ). ầ ề ầ

ng đi ph i n m * N u ế n lẻ thì đi m đ u và đi m cu i c a đ ầ ố ủ ườ ể ả ằ ở ề ể

2 ph n khác nhau (chúng li n k v i nhau). ầ

Mà khi xu t phát t ề ừ ề ớ ỉ ầ ỗ

ồ 1 đ nh ta luôn có 3 cách đi(do m i ph n g m ng đi có đ dài n gi a 2 đ nh là: ỉ ắ ố ườ ữ ộ ỉ

n-1(do c nh cu i cùng n i v i đ nh cu i ch có 1 cách) ố ớ ỉ

ố

ỉ

ụ ế ề

ẻ

n-1(do c nh cu i cùng n i v i đ nh cu i ch có 1 cách) ố ớ ỉ

ạ

ố

ỉ

ấ 3 đ nh). Áp d ng quy t c nhân ta có s đ - N u 2 đ nh li n k : ề ỉ + n ch n: d=0 ẵ + n l : d=3 ạ - N u 2 đ nh không li n k : ề ế ề

ỉ + n ch n : d=3 ẵ : d=0 + n l ẻ

Áp d ng c th : ụ ể ụ

Đ dài n=2 n=3 n=4 n=5 ộ

Đ nhỉ

ề

1, V2, V3, V4,

d=0 d=3 d=9 d=0 d=0 d=27 d=81 d=0 Li n kề Không li n kề ề

ề ề ứ ự các đ nh V ỉ

* Cách 2: Đ th K3,3 có ma tr n li n k theo th t ậ ồ ị V5, V6 nh sau: ư

0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0

ề Cho G là m t đ th (vô h ng ho c có h ặ ướ

ề ề

ng,

Ta có m nh đ : ệ v i ma tr n li n k A theo th t ứ ự ậ ớ ừ i t đ v ng đi khác nhau đ dài r t ườ ộ b ng giá tr c a ph n t ộ ầ ử ằ ậ

ng) ướ ộ ồ ị 1, v2, ..., vn. Khi đó s cácố các đ nh v ỉ i vớ j trong đó r là m t s nguyên d ươ ộ ố r. dòng i c t j c a ma tr n A ủ n

ị ủ Ta có:

An = A.A...A.A

3n-1 3n-1 3n-1 0 0 0

A= , n u n ch n ế ẵ

3n-1 3n-1 0 0 0 3n-1 3n-1 0 0 0 3n-1 3n-1 0 0 0 0 0 3n-1 3n-1 3n-1 0 0 3n-1 3n-1 3n-1 0 0 3n-1 3n-1 3n-1

A= , n u n l ế ẻ

0 0 0 3n-1 3n-1 3n-1 0 0 0 3n-1 3n-1 3n-1 0 0 0 3n-1 3n-1 3n-1 3n-1 3n-1 3n-1 0 0 0 3n-1 3n-1 3n-1 0 0 0 3n-1 3n-1 3n-1 0 0 0

ng h p c th ư ậ ụ ườ ợ ụ ể

cách 1. Nh v y, theo m nh đ trên, áp d ng vào các tr ề đ bài đã cho ta có k t qu nh ề ệ ả ư ở ế

ế ự ỗ ấ ạ

ể ằ

ườ ế ồ ể ắ ườ ể ỗ

* Bài 12: M t cu c h p có ít nh t 3 đ i bi u đ n d .M i ng i quen ít ộ ể ộ ọ ộ ố ạ nh t 2 đ i bi u khác.Ch ng minh r ng có th s p x p m t s đ i ứ ạ ấ bi u ng i xung quanh m t bàn tròn đ m i ng ữ i ng i gi a 2 ể ộ ồ ng ườ i mà đ i bi u đó quen. ể ạ

ờ ả

i: * Ta có th bi u di n m i quan h c a các đ i bi u đ n tham d ệ ủ L i gi ố ế ể ạ ự ễ

ộ ọ ồ ị ằ

ể ạ

ể ể cu c h p b ng đ n đ th G=(V,E). ơ ố ạ ỉ ớ G có n đ nh (n≥3, n là s đ i bi u) và e c nh. ạ M i đ nh c a đ th ng v i 1 đ i bi u, gi a 2 đ nh ng v i 2 đ i ạ ỉ ứ ỗ ỉ ữ ể ớ

ể ồ ạ

ủ ồ ị ứ i 1 c nh. ạ ỉ ể ạ ớ

ườ

bi u quen nhau t n t i (i=1,2,...,n): đ nh c a đ th ( ng v i 1 đ i bi u) G i Vọ ủ ồ ị ứ Do m i ng i quen ít nh t 2 đ i bi u khác nên ể ạ ấ ỗ deg(Vi) ≥ 2 n

∑deg(Vi) ≥ 2n

i=1

ố ạ

* M t khác, theo đ ra ta có: các đ i bi u ng i xung quanh 1 bàn S c nh c a đ th : e ≥ n ủ ồ ị ề ặ (1) ạ ể ồ

tròn.

ể Vì v y, đ th bi u di n cách s p x p ch ng i c a các đ i bi u ắ ồ ủ ế ạ ỗ ậ

ầ ỏ

ồ ị ể th a yêu c u là đ th vòng C ồ ị Trong đ th vòng C ồ ị ạ ạ e c nh

ể

ạ

ể

ạ (do nó bi u th m i quan h gi a các đ i bi u) ễ n. n có n (c nh), n c nh này đ ệ ữ c l y t ượ ấ ừ (2) c a Gủ

.(Cn

ậ ỉ ằ ằ

ị ố * T p đ nh c a G và C ủ T (1), (2) và (3) cho th y, C

n là đ th con bao hàm c a G

c t o ra b ng cách b đi m t s c nh thích h p c a G)

n b ng nhau và b ng n. ấ ộ ố ạ

ượ ạ

ằ

ỏ

ừ (3) ủ

V y, d a trên m i quan h gi a các đ i bi u nh trên ta có th ồ ị ợ ủ ạ ậ ự ệ ữ

ể ữ i ng i gi a 2 ể ỗ ố ồ ể ạ ồ

ư s p x p các đ i bi u ng i quanh bàn tròn sao cho m i ng ườ ắ ng ế i mà h quen.( Đpcm) ườ ọ

ỗ ọ ớ ấ ớ

ằ ứ

ộ ể ỗ ộ ố ẵ ữ ể ế ồ ọ

*Bài 13: ấ M tộ l p h c có ít nh t 4 sinh viên. M i sinh viên thân v i ít nh t 3 sinh viên khác. Ch ng minh r ng có th x p m t s ch n sinh viên ng i ồ quanh m t cái bàn tròn đ m i sinh viên ng i gi a 2 sinh viên mà h thân . L i gi ờ ả

ể ể ễ ố ớ

ệ ữ ỉ ơ ố

1 đ n đ th G=(V,E) n đ nh(n≥4, n: s sinh viên), e c nh. ạ ề ớ ớ

ề ớ

i: * M i quan h gi a các sinh viên trong l p có th bi u di n b ng ằ ồ ị Hai đ nh ng v i 2 sinh viên thân nhau li n k v i nhau. G i Vọ M i sinh viên thân v i ít nh t 3 ng ỗ ỉ ứ i (i=1,2,...,n): đ nh c a đ th ng v i 1 sinh viên. ủ ồ ị ứ i ườ ỉ ớ ấ

(1) ố ạ

n (do các sinh viên ng i quanh

* M t khác, theo đ ra ta có: cách s p x p ch ng i c a các sinh ề ắ ế ỗ

deg(Vi) ≥ 3 n ∑ deg(Vi) ≥ 3n i=1 T ng s c nh c a G là: e ≥ 3n/2 ủ ổ ặ ể ể ồ ủ ồ ồ ị ằ

viên có th bi u di n b ng đ th vòng C ễ bàn tròn).

e c nh c a G) ủ ạ

ạ ả ẵ

Cn có n c nh (n c nh này l y t ạ ấ ừ Mà e ph i là s nguyên suy ra n ph i chia h t cho 2 (n ch n) ế ố ả n và G b ng nhau và b ng n. T p đ nh c a C ủ ậ ằ ằ ỉ

.(Cn có th t o ra t

ể ạ

ừ G

n chính là đ th con bao hàm c a G

ủ ấ ừ

Hay: có th s p x p m t s ch n sinh viên ng i quanh m t cái

ộ ố ạ ể ắ bàn tròn sao cho m i ng ỗ

ộ ồ i mà h thân.( Đpcm) T đó, ta th y C ồ ị b ng cách b đi m t s c nh thích h p) ợ ỏ ằ ộ ố ẵ ế i ng i gi a 2 ng ữ ồ ườ ọ ườ

ứ ằ

* Bài 14: Trong m t cu c h p có đúng 2 đ i bi u không quen nhau và m i ỗ ạ ể ộ i quen đ n d .Ch ng minh r ng luôn luôn ế ự ể ữ ạ

ườ ể ộ ố ạ ể ế i ng i gi a 2 ng ữ ồ ườ

ệ ữ ố

ự ộ ọ ộ ạ ể ơ

ỗ ỉ i 1 c nh. ạ ễ ằ ỉ ứ ể ớ

ạ

ộ ọ ng đ i bi u này có m t s l ộ ố ẻ ườ ạ ể ỗ có th x p m t s đ i bi u ng i chen gi a 2 đ i bi u nói trên, đ m i ồ ể i mà đ i bi u đó quen. ng ể ạ i: L i gi ờ ả ể ể M i quan h gi acác đ i bi u đ n tham d cu c h p có th bi u ế ể ạ di n b ng 1 đ n đ th G=(V,E).Trong đó m i đ nh là m t đ i bi u, gi a ữ ồ ị 2 đ nh ng v i 2 đ i bi u quen nhau t n t ồ ạ ạ Trong cu c h p có đúng 2 đ i bi u không quen nhau và có s l ố ẻ ể ộ ọ i quen đ n tham d .V y G có đúng 2 đ nh không li n k và 2 đ nh ỉ ự ậ ề ề ỉ ườ

ng này có b c l

ế ề: N u m t đ th có đúng hai đ nh b c l ậ ẻ ỉ ỉ ế . ậ ẻ T ừ m nh đ ệ

ả thì hai đ nh ta suy ra có th tìmể

ng đi n i chúng ố ể ạ

ể ớ

ứ ồ ườ i mà đ i bi u đó quen.(do 2 đ nh ng v i 2 ng i ạ ườ i không ng i sát nhau và h quen v i n-2 ỉ ứ ọ ườ ồ ớ

i còn l ộ ồ ị này ph i liên thông, t c là có m t đ ộ ườ ra m t s đ i bi u ng i chen vào gi a 2 đ i bi u này sao cho m i đ i ỗ ạ ộ ố ạ ữ ể bi u ng i gi a 2 ng ể ữ ồ này không liên thông, 2 ng i) ng ạ ườ

‡ M t thành ph có n (n ộ

ề ố ầ ớ

*Bài 15: ố ố ườ ứ ng ng m t ầ ằ

ng ng m. kỳ đ u có s đ u m i đ đ u không nh h n n. Ch ng minh r ng t ề th đi đ n m t nút giao thông b t kỳ khác b ng đ ể ỏ ơ ộ ế ấ ườ

2) nút giao thông và hai nút giao thông b tấ i m t trong các nút giao thông này ộ m t nút giao thông tuỳ ý ta có ừ ộ ằ ầ i:

L i gi ờ ả ộ ơ ng ng m c a thành ph là m t đ n ầ ủ ố ể ệ ố ườ

ỉ

- Ta có th xem h th ng đ đ th có các đ nh là các nút giao thông. ồ ị ủ ồ ị

ố ỉ ạ ố ầ ườ ố

S đ nh c a đ th chính là s nút giao thông: n (n≥2) C nh c a đ th là đ ng ng m n i 2 nút giao thông. ủ ồ ị Theo đ ra ta có: ề Hai nút giao thông b t kì đ u có s đ u m i đ ề ấ ố ườ ng ng m t ầ ớ i

ố ầ m t trong các nút giao thông đ u không nh h n n. ỏ ơ ề ộ

- Ta có m nh đ : ề

M i đ n đ th n đ nh (n≥2) có t ng b c c a 2 đ nh tùy ý ồ ị ỉ ậ ủ ổ ỉ

ệ ọ ơ không nh h n n đ u là đ th liên thông. ề ồ ị

V y, theo đ nh lí trên, h th ng đ ng ng m c a thành ph là đ ệ ố ị ườ ủ ầ ố ồ ỏ ơ ậ

th liên thông. ị

ể ế ộ

ng ng m.(Đpcm). thông b t kỳ khác b ng đ Suy ra, từ m t nút giao thông tuỳ ý ta có th đi đ n m t nút giao ấ ộ ằ ườ ầ

ồ ị ẳ ấ ớ ỉ

*Bài 16: Có bao nhiêu đ n đ th đ ng c u v i n đ nh khi: a) n=2 ơ b) n=3 c) n=4

i: L i gi

a) V i n=2, có 2 đ n đ th không đ ng c u nh sau: ồ ị và