Chu
.
o
.
ng 2
C´ac sˆo
´
co
.
ba
˙’
n cu
˙’
a d¯ˆo
`
thi
.
2.1 Chu sˆo
´
Kh´ai niˆe
.
m m`a ch´ung ta s˜e d¯ˆe
`
cˆa
.
p o
.
˙’
d¯ˆay khˆong phu
.

.
´o
.
ng G := (V, E) c´o n d¯ı
˙’
nh, m
ca
.
nh v`a p th`anh phˆa
`
n liˆen thˆong. D
-
ˇa
.
t
ρ(G) := n − p,
ν(G) := m − ρ(G) = m − n + p.
Ta go
.
i ν(G) l`a chu sˆo
´
cu
˙’
a d¯ˆo
`
thi
.
G.
D
-

G
bˇa
`
ng c´ach nˆo
´
i hai d¯ı
˙’
nh a v`a b cu
˙’
a G bo
.
˙’
i mˆo
.
t ca
.
nh m´o
.
i; nˆe
´
u a v`a b tr`ung nhau hoˇa
.
c c´o thˆe
˙’
nˆo
´
i v´o
.
i nhau bo
.

) = ρ(G) + 1, ν(G

) = ν(G).
Ch´u
.
ng minh. Theo c´ach xˆay du
.
.
ng, d¯a d¯ˆo
`
thi
.
G

c´o n

= n d¯ı
˙’
nh, m

= m + 1 ca
.
nh v`a gia
˙’
su
.
˙’
G

c´o p

c l`a p = p

. Do d¯´o
ρ(G

) = n

− p

= n − p = ρ(G),
ν(G

) = m

− ρ(G

) = ν(G) + 1.
49

Ngu
.
o
.
.
c la
.
i, nˆe
´
u a = b v`a khˆong tˆo
`

qua
˙’
2.1.2 ρ(G) ≥ 0 v`a ν(G) ≥ 0.
Ch´u
.
ng minh. Thˆa
.
t vˆa
.
y, xuˆa
´
t ph´at t`u
.
d¯ˆo
`
thi
.
th`anh lˆa
.
p bˇa
`
ng c´ac d¯ı
˙’
nh cu
˙’
a d¯a d¯ˆo
`
thi
.
vˆo

.
˙’
i d¯ˆa
`
u ta
c´o ρ = 0, ν = 0; mˆo
˜
i khi thˆem mˆo
.
t ca
.
nh, th`ı hoˇa
.
c ρ tˇang v`a l´uc d¯´o ν khˆong d¯ˆo
˙’
i, hoˇa
.
c ν tˇang
v`a l´uc d¯´o ρ khˆong d¯ˆo
˙’
i. Nhu
.
vˆa
.
y, trong qu´a tr`ınh xˆay du
.
.
ng d¯ˆo
`
thi

.
i sˆo
´
vector trong viˆe
.
c nghiˆen c´u
.
u,
ngu
.
`o
.
i ta thu
.
`o
.
ng d¯ˇa
.
t tu
.
o
.
ng ´u
.
ng mˆo
˜
i chu tr`ınh trong G v´o
.
i mˆo
.

.
nh e
k
, r
k
lˆa
`
n thuˆa
.
n hu
.
´o
.
ng v`a s
k
lˆa
`
n ngu
.
o
.
.
c hu
.
´o
.
ng th`ı ta d¯ˇa
.
t c
k

.
o
.
ng ´u
.
ng v´o
.
i µ v`a k´y hiˆe
.
u l`a µ (hay l`a µ nˆe
´
u khˆong thˆe
˙’
gˆay ra
nhˆa
`
m lˆa
˜
n).
C´ac chu tr`ınh µ, µ

, µ

, . . . go
.
i l`a d¯ˆo
.
c lˆa
.
p nˆe

-
i
.
nh l´y 2.1.3 Chu sˆo
´
ν(G) cu
˙’
a G = (V, E) bˇa
`
ng sˆo
´
cu
.
.
c d¯a
.
i c´ac chu tr`ınh d¯ˆo
.
c lˆa
.
p.
Ch´u
.
ng minh. Tiˆe
´
n h`anh nhu
.
trong Hˆe
.
qua


bˇa
`
ng c´ach thˆem t`u
.
ng ca
.
nh
mˆo
.
t v`ao. Theo D
-
i
.
nh l´y 2.1.1, chu sˆo
´
s˜e tˇang mˆo
.
t d¯o
.
n vi
.
nˆe
´
u ca
.
nh thˆem v`ao lˆa
.
p ra c´ac chu
tr`ınh m´o

.
nh e
k
ta d¯˜a c´o mˆo
.
t co
.
so
.
˙’
gˆo
`
m c´ac chu tr`ınh d¯ˆo
.
c lˆa
.
p:
µ
1
, µ
2
, µ
3
, . . . ; v`a sau khi thˆem ca
.
nh e
k
xuˆa
´
t hiˆe


tu
.
o
.
ng ´u
.
ng c´ac chu tr`ınh µ
j
c´o th`anh phˆa
`
n th´u
.
k bˇa
`
ng khˆong, trong khi vector tu
.
o
.
ng ´u
.
ng
chu tr`ınh γ
1
c´o th`anh phˆa
`
n th´u
.
k kh´ac khˆong). Mˇa
.

.
n vi
.
th`ı sˆo
´
cu
.
.
c
d¯a
.
i c´ac chu tr`ınh d¯ˆo
.
c lˆa
.
p tuyˆe
´
n t´ınh c˜ung tˇang lˆen mˆo
.
t d¯o
.
n vi
.
. D
-
i
.
nh l´y d¯u
.
o

´
u v`a chı
˙’
nˆe
´
u ν(G) = 0.
(b) D
-
a d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng G c´o d¯´ung mˆo
.
t chu tr`ınh nˆe
´
u v`a chı
˙’
nˆe
´
u ν(G) = 1.
D
-
i
.
nh l´y 2.1.5 Trong d¯ˆo

Ch´u
.
ng minh. Thˆa
.
t vˆa
.
y, x´et d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng lˆa
.
p bo
.
˙’
i c´ac cung kh´ac nhau cu
˙’
a G (mˆo
˜
i cung
tu
.
o
.
ng ´u
.

˙’
i n´o, tˆa
.
p S

c´ac d¯ı
˙’
nh
c´o hai cung cu
˙’
a µ ra kho
˙’
i n´o v`a tˆa
.
p S

c´ac d¯ı
˙’
nh c´o hai cung cu
˙’
a µ d¯i t´o
.
i n´o. V`ı sˆo
´
c´ac cung
d¯i ra bˇa
`
ng sˆo
´
c´ac cung d¯i t´o


1
, v

2
, . . . , v

k
l`a c´ac phˆa
`
n tu
.
˙’
cu
˙’
a S

.
Trˆen chu tr`ınh µ, c´ac phˆa
`
n tu
.
˙’
cu
˙’
a S

v`a cu
˙’
a S

´
u µ
0
l`a mˆo
.
t d¯u
.
`o
.
ng d¯i gˇa
.
p
d¯ı
˙’
nh x tru
.
´o
.
c d¯ı
˙’
nh y th`ı ta k´y hiˆe
.
u µ
0
[x, y] l`a d¯u
.
`o
.
ng d¯i bˆo
.

v`a d`ung c´ac cung cu
˙’
a µ d¯ˆe
˙’
d¯i t`u
.
v

i+1
d¯ˆe
´
n v

i
. Chu tr`ınh µ l`a mˆo
.
t tˆo
˙’
ho
.
.
p tuyˆe
´
n t´ınh cu
˙’
a c´ac ma
.
ch v`ı ta c´o thˆe
˙’
viˆe

1
[v

1
, v

2
] + µ[v

2
, v

2
] + µ
2
[v

2
, v

3
] + · · · − (µ
1
+ µ
2
+ · · ·).
Vˆa
.
y mo
.

.
p tuyˆe
´
n t´ınh cu
˙’
a c´ac chu tr`ınh so
.
cˆa
´
p).
Trong R
m
, c´ac ma
.
ch lˆa
.
p th`anh mˆo
.
t co
.
so
.
˙’
cu
˙’
a khˆong gian vector con sinh bo
.
˙’
i c´ac chu
tr`ınh, v`a theo D

n t´ınh bˇa
`
ng ν(G). 
51

2.2 Sˇa
´
c sˆo
´
Gia
˙’
su
.
˙’
rˇa
`
ng ch´ung ta c´o mˆo
.
t d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng G v´o
.
i n d¯ı
˙’

t ra la
.
i khˆong mang t´ınh thu
.
.
c tiˆe
˜
n. Thˆe
´
th`ı sˆo
´
m`au tˆo
´
i thiˆe
˙’
u
d¯`oi ho
˙’
i l`a bao nhiˆeu? D
-
ˆay ch´ınh l`a b`ai to´an tˆo m`au. Khi c´ac d¯ı
˙’
nh d¯u
.
o
.
.
c tˆo, ch´ung ta c´o thˆe
˙’
nh´om ch´ung v`ao c´ac tˆa

ˆay ch´ınh l`a b`ai to´an phˆan hoa
.
ch. B`ai to´an tˆo m`au v`a
phˆan hoa
.
ch d˜ı nhiˆen c´o thˆe
˙’
x´et trˆen c´ac ca
.
nh cu
˙’
a d¯ˆo
`
thi
.
. Trong tru
.
`o
.
ng ho
.
.
p d¯ˆo
`
thi
.
phˇa
˙’
ng
thˆa

.
c mˆo
.
t sˆo
´
nguyˆen p, ta n´oi rˇa
`
ng d¯ˆo
`
thi
.
G l`a p−sˇa
´
c nˆe
´
u bˇa
`
ng p
m`au kh´ac nhau ta c´o thˆe
˙’
tˆo m`au c´ac d¯ı
˙’
nh, sao cho hai d¯ı
˙’
nh kˆe
`
nhau khˆong c`ung mˆo
.
t m`au.
Sˆo

2.2.2 H`ınh 2.1 minh ho
.
a ba c´ach tˆo m`au kh´ac nhau cu
˙’
a d¯ˆo
`
thi
.
. Dˆe
˜
d`ang kiˆe
˙’
m tra
rˇa
`
ng d¯ˆo
`
thi
.
n`ay l`a 2−sˇa
´
c.
b
r
•
•
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
b
r
•
•
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
b
r

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
t ba
˙’
n d¯ˆo
`
. Go
.
i V l`a tˆa
.
p ho
.
.
p c´ac
nu
.
´o
.
c, d¯ˇa
.
t (i, j) ∈ E nˆe
´
u c´ac nu
.
´o
.
c i v`a j c´o biˆen gi´o
.
i chung. D
-
ˆo

.
i c´ac d¯ı
˙’
nh chung); n´oi c´ach kh´ac, G l`a d¯ˆo
`
thi
.
phˇa
˙’
ng. Ngu
.
`o
.
i ta d¯˜a biˆe
´
t rˇa
`
ng sˇa
´
c
sˆo
´
cu
˙’
a mo
.
i d¯ˆo
`
thi
.

˙’
tˆo m`au ba
˙’
n d¯ˆo
`
phˇa
˙’
ng sao cho hai nu
.
´o
.
c kˆe
`
nhau khˆong c`ung mˆo
.
t m`au.
52

T`u
.
d¯i
.
nh ngh˜ıa dˆe
˜
d`ang suy ra
1. Mˆo
.
t d¯ˆo
`
thi

´ıt nhˆa
´
t bˇa
`
ng
hai.
3. D
-
ˆo
`
thi
.
d¯ˆa
`
y d¯u
˙’
n d¯ı
˙’
nh K
n
l`a n−sˇa
´
c.
4. D
-
ˆo
`
thi
.
l`a mˆo

.
2−sˇa
´
c l`a hai phˆa
`
n do ch´ung ta c´o thˆe
˙’
phˆan hoa
.
ch tˆa
.
p c´ac d¯ı
˙’
nh
V th`anh hai tˆa
.
p con theo m`au d¯u
.
o
.
.
c tˆo trˆen c´ac d¯ı
˙’
nh. Tu
.
o
.
ng tu
.
.

ng: d¯ˆo
`
thi
.
c´o ´ıt nhˆa
´
t hai d¯ı
˙’
nh cˆo lˆa
.
p v`a
khˆong c´o ca
.
nh l`a hai phˆa
`
n nhu
.
ng l`a 1−sˇa
´
c.
D
-
i
.
nh ngh˜ıa 2.2.4 Ta go
.
i sˇa
´
c l´o
.

`
u n`ay khˆong thˆe
˙’
l`am d¯u
.
o
.
.
c v´o
.
i (q − 1) m`au.
Nhˆa
.
n x´et rˇa
`
ng sˇa
´
c l´o
.
p cu
˙’
a d¯ˆo
`
thi
.
G = (V, E) ch´ınh l`a sˇa
´
c sˆo
´
cu

.
o
.
ng ´u
.
ng mˆo
.
t ca
.
nh cu
˙’
a G; ca
.
nh e

= (v

1
, v

2
) ∈ E

nˆe
´
u c´ac ca
.
nh e
1
v`a e

a vˆe
`
b`ai to´an sˇa
´
c sˆo
´
. Du
.
´o
.
i d¯ˆay l`a mˆo
.
t v`ai kˆe
´
t qua
˙’
co
.
ba
˙’
n
vˆe
`
sˇa
´
c sˆo
´
.
D
-

iˆe
`
u kiˆe
.
n cˆa
`
n. Nˆe
´
u d¯ˆo
`
thi
.
G l`a 2−sˇa
´
c, th`ı tˆa
´
t nhiˆen G khˆong ch´u
.
a chu
tr`ınh c´o d¯ˆo
.
d`ai le
˙’
, v`ı c´ac d¯ı
˙’
nh cu
˙’
a mˆo
.
t chu tr`ınh loa

su
.
˙’
d¯ˆo
`
thi
.
G khˆong c´o chu tr`ınh c´o d¯ˆo
.
d`ai le
˙’
, ta ch´u
.
ng minh n´o l`a 2−sˇa
´
c.
Khˆong gia
˙’
m tˆo
˙’
ng qu´at coi G l`a liˆen thˆong. Ta s˜e tˆo m`au dˆa
`
n c´ac d¯ı
˙’
nh cu
˙’
a G theo quy tˇa
´
c
sau:

i n´o; nˆe
´
u
d¯ı
˙’
nh y d¯˜a d¯u
.
o
.
.
c tˆo d¯o
˙’
, th`ı ta tˆo xanh tˆa
´
t ca
˙’
c´ac d¯ı
˙’
nh kˆe
`
v´o
.
i y.
V`ı d¯ˆo
`
thi
.
G liˆen thˆong, nˆen s´o
.
m hay muˆo

c tˆo xanh v`a tˆo d¯o
˙’
, v`ı nhu
.
vˆa
.
y th`ı x v`a a s˜e c`ung
nˇa
`
m trˆen mˆo
.
t chu tr`ınh c´o d¯ˆo
.
d`ai le
˙’
. Vˆa
.
y d¯ˆo
`
thi
.
G l`a 2−sˇa
´
c. 
Ch´u ´y rˇa
`
ng t´ınh chˆa
´
t d¯ˆo
`

˙’
. Thˆa
.
t vˆa
.
y gia
˙’
su
.
˙’
c´o mˆo
.
t chu tr`ınh
µ = {v
0
, v
1
, . . . , v
p
= v
0
}
c´o d¯ˆo
.
d`ai p le
˙’
. Mˆo
˜
i khi gˇa
.

k
, . . . , v
0
}; ho
.
n n˜u
.
a mˆo
.
t trong
hai chu tr`ınh c´o d¯ˆo
.
d`ai le
˙’
(v`ı nˆe
´
u khˆong nhu
.
thˆe
´
th`ı µ s˜e c´o d¯ˆo
.
d`ai chˇa
˜
n). Ta thˆa
´
y rˇa
`
ng nˆe
´

d`ai le
˙’
; v`ı cuˆo
´
i c`ung mo
.
i chu tr`ınh d¯ˆe
`
u l`a so
.
cˆa
´
p, nˆen xa
˙’
y
ra mˆau thuˆa
˜
n; v`a ta c´o d¯iˆe
`
u cˆa
`
n ch´u
.
ng minh.
D
-
i
.
nh l´y sau d¯ˆay cho ta biˆe
´

max
.
Ch´u
.
ng minh. B`ai tˆa
.
p. 
Brooks [9] d¯˜a ch´u
.
ng minh rˇa
`
ng nˆe
´
u G l`a d¯ˆo
`
thi
.
khˆong d¯ˆa
`
y d¯u
˙’
, c´o d
max
d¯ı
˙’
nh th`ı
γ(G) ≤ d
max
.
2.2.1 C´ach t`ım sˇa

.
c nghiˆe
.
m rˆa
´
t d¯o
.
n gia
˙’
n, ´ap du
.
ng tru
.
.
c tiˆe
´
p d¯u
.
o
.
.
c, nhu
.
ng khˆong pha
˙’
i l´uc n`ao
c˜ung c´o hiˆe
.
u qua
˙’

.
54

Phu
.
o
.
ng ph´ap thu
.
.
c nghiˆe
.
m
Bˇa
`
ng c´ach tˆo m`au t`uy ´y d`ung c´ac m`au 1, 2, . . . , p v`a t`ım c´ach loa
.
i dˆa
`
n mˆo
.
t m`au n`ao d¯´o (go
.
i
l`a “m`au t´o
.
i ha
.
n”) trong c´ac m`au ˆa
´

i ha
.
n j v`a
k. Ta c´o thˆe
˙’
lˆa
.
p t´u
.
c thay m`au cu
˙’
a d¯ı
˙’
nh v nˆe
´
u c´ac tˆa
.
p ho
.
.
p C
jk
1
∩ Γ(v), C
jk
2
∩ Γ(v), . . . khˆong
pha
˙’
i l`a hai m`au: lˆa

´
i c`ung tˆo d¯ı
˙’
nh v m`au j (l´uc n`ay d¯ı
˙’
nh v khˆong kˆe
`
v´o
.
i d¯ı
˙’
nh n`ao c´o
m`au j).
Phu
.
o
.
ng ph´ap gia
˙’
i t´ıch
Kiˆe
˙’
m tra bˇa
`
ng c´ach gia
˙’
i t´ıch xem d¯ˆo
`
thi
.

.
ng ´u
.
ng v´o
.
i mˆo
.
t hˆe
.
thˆo
´
ng c´ac sˆo
´
x
ij
, i = 1, 2, . . . , n; j = 1, 2, . . . , p, d¯u
.
o
.
.
c x´ac d¯i
.
nh nhu
.
sau:
x
ij
=

1 nˆe

u ca
.
nh e
j
liˆen thuˆo
.
c d¯ı
˙’
nh v
i
,
0 trong tru
.
`o
.
ng ho
.
.
p ngu
.
o
.
.
c la
.
i.
L´uc d¯´o b`ai to´an tro
.
˙’
th`anh t`ım c´ac sˆo

t d¯ˇa
˙’
ng th´u
.
c tuyˆe
´
n t´ınh. Dˆe
˜
r`ang thˆa
´
y rˇa
`
ng hˆe
.
d¯´o th´ıch ho
.
.
p v´o
.
i c´ac phu
.
o
.
ng
ph´ap thˆong thu
.
`o
.
ng cu
˙’

˙’
n d¯i
.
nh trong
V´o
.
i d¯ˆo
`
thi
.
G = (V, Γ) cho tru
.
´o
.
c ta thu
.
`o
.
ng quan tˆam d¯ˆe
´
n tˆa
.
p con cu
˙’
a V c´o nh˜u
.
ng t´ınh chˆa
´
t
n`ao d¯´o. Chˇa

y d¯u
˙’
? Hoˇa
.
c t`ım tˆa
.
p con c´ac d¯ı
˙’
nh cu
˙’
a d¯ˆo
`
thi
.
G c´o sˆo
´
phˆa
`
n tu
.
˙’
nhiˆe
`
u nhˆa
´
t sao cho
hai d¯ı
˙’
nh trong d¯´o khˆong kˆe
`

C´ac sˆo
´
v`a c´ac tˆa
.
p con tu
.
o
.
ng ´u
.
ng l`o
.
i gia
˙’
i c´ac b`ai to´an trˆen cho nh˜u
.
ng t´ınh chˆa
´
t quan
trong cu
˙’
a d¯ˆo
`
thi
.
v`a c´o nhiˆe
`
u ´u
.
ng du

d¯iˆe
.
n tu
.
˙’
, v.v.
D
-
i
.
nh ngh˜ıa 2.3.1 X´et d¯ˆo
`
thi
.
vˆo hu
.
´o
.
ng G := (V, Γ); tˆa
.
p ho
.
.
p S ⊂ V d¯u
.
o
.
.
c go
.

˙’
nh a, b ∈ S th`ı b /∈ Γ(a).
K´y hiˆe
.
u S l`a ho
.
c´ac tˆa
.
p ˆo
˙’
n d¯i
.
nh trong cu
˙’
a d¯ˆo
`
thi
.
G. Khi d¯´o
1. Tˆa
.
p trˆo
´
ng ∅ thuˆo
.
c S.
2. Nˆe
´
u S ∈ S v`a A ⊂ S th`ı A ∈ S. N´oi c´ach kh´ac, tˆa
.

.
i nˆe
´
u thˆem mˆo
.
t d¯ı
˙’
nh bˆa
´
t k`y v`ao n´o th`ı s˜e khˆong c`on ˆo
˙’
n d¯i
.
nh
trong n˜u
.
a. D
-
a
.
i lu
.
o
.
.
ng
α(G) := max{#S | S ∈ S}
d¯u
.
o

˙’
n d¯i
.
nh trong nhu
.
ng
khˆong cu
.
.
c d¯a
.
i; tˆa
.
p {v
7
, v
8
, v
2
, v
5
} l`a ˆo
˙’
n d¯i
.
nh trong cu
.
.
c d¯a
.

p ˆo
˙’
n d¯i
.
nh trong
cu
.
.
c d¯a
.
i. Ho
.
c´ac tˆa
.
p ˆo
˙’
n d¯i
.
nh trong cu
.
.
c d¯a
.
i cu
˙’
a d¯ˆo
`
thi
.
n`ay l`a

, v
4
}, {v
3
, v
7
, v
8
}.
V´ı du
.
2.3.3 [Gauss] B`ai to´an t´am con hˆa
.
u. Trˆen b`an c`o
.
c´o thˆe
˙’
bˆo
´
tr´ı t´am con hˆa
.
u, sao
cho khˆong c´o con n`ao ch´em d¯u
.
o
.
.
c con n`ao khˆong? B`ai to´an nˆo
˙’
i tiˆe

´o
.
ng c´o 64 d¯ı
˙’
nh (l`a c´ac ˆo trˆen b`an c`o
.
), trong
d¯´o y ∈ Γ(x) nˆe
´
u c´ac ˆo x v`a y nˇa
`
m trˆen c`ung mˆo
.
t h`ang, mˆo
.
t cˆo
.
t hay mˆo
.
t d¯u
.
`o
.
ng ch´eo. Thu
.
.
c
tˆe
´
, kh´o khˇan la

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

v
6
v
7
v
8
• • •
•
•
•
•
•
H`ınh 2.2:
gia
˙’
i, c`on t`o
.
b´ao vˆe
`
c`o
.
o
.
˙’
Berlin“Schachzeitung” nˇam 1854 chı
˙’
m´o
.
i d¯u
.

(72631485) (61528374) (58417263)
(35841726) (46152837) (57263148)
(16837425) (57263184) (48157263)
(51468273) (42751863) (35281746)
Mˆo
˜
i so
.
d¯ˆo
`
trˆen tu
.
o
.
ng ´u
.
ng v´o
.
i mˆo
.
t ho´an vi
.
, v`a t`u
.
mˆo
.
t so
.
d¯ˆo
`

i so
.
d¯ˆo
`
nhˆa
.
n d¯u
.
o
.
.
c qua d¯u
.
`o
.
ng ch´eo ch´ınh; ho´an vi
.
cuˆo
´
i c`ung (35281746) chı
˙’
c´o bˆo
´
n
l`o
.
i gia
˙’
i v`ı so
.

Nˆe
´
u V l`a mˆo
.
t tˆa
.
p ho
.
.
p ngu
.
`o
.
i, v`a b ∈ Γ(a) chı
˙’
su
.
.
d¯ˆo
`
ng t`ınh gi˜u
.
a a v`a b, th`ı thu
.
`o
.
ng yˆeu cˆa
`
u
t`ım b`e cu

b ∈ Γ(a

) nˆe
´
u v`a chı
˙’
nˆe
´
u b /∈ Γ(a).
B`ai to´an quy vˆe
`
t`ım mˆo
.
t tˆa
.
p ho
.
.
p ˆo
˙’
n d¯i
.
nh trong cu
.
.
c d¯a
.
i cu
˙’
a d¯ˆo

sau: mˆo
.
t k´y t´uc x´a nuˆoi du
.
˜o
.
ng 15 cˆo g´ai, k´y hiˆe
.
u l`a a, b, c, d, e, f, g, h, i, j, k, l, m, n, o;
h`ang ng`ay c´ac cˆo d¯i da
.
o cho
.
i th`anh t`u
.
ng bˆo
.
ba, c´o thˆe
˙’
d¯u
.
a c´ac cˆo d¯i cho
.
i trong ba
˙’
y ng`ay
liˆe
`
n sao cho khˆong c´o hai cˆo n`ao c`ung d¯i trong mˆo
.

sau:
57

Chu
˙’
Nhˆa
.
t Th´u
.
Hai Th´u
.
Ba Th´u
.
Tu
.
Th´u
.
Nˇam Th´u
.
S´au Th´u
.
Ba
˙’
y
afk abe alm ado agn ahj aci
bgl cno bcf bik bdj bmn bho
chm dfl deh cjl cek cdg dkm
din ghk gio egm fmo fei eln
ejo ijm jkn fhn hil klo fgj
B`ai to´an vˆe

.
.
t lˆa
.
p 35 bˆo
.
ba kh´ac nhau sao cho khˆong c´o hai cˆo
n`ao c`ung trong mˆo
.
t bˆo
.
ba qu´a mˆo
.
t lˆa
`
n khˆong? D
-
ˆe
˙’
gia
˙’
i b`ai to´an bˆo
˙’
tro
.
.
, chı
˙’
cˆa
`

p ho
.
.
p ˆo
˙’
n d¯i
.
nh trong cu
.
.
c d¯a
.
i. Ta c´o α(G) ≤ 35 v`ı mˆo
.
t cˆo
g´ai chı
˙’
c´o mˇa
.
t nhiˆe
`
u nhˆa
´
t l`a trong 7 bˆo
.
ba kh´ac nhau, nˆen tˆa
´
t ca
˙’
c´o 15 × 7 ×

.
i.
D
-
ˆe
˙’
x´et xem mˆo
.
t l`o
.
i gia
˙’
i n`ao d¯´o cu
˙’
a b`ai to´an bˆo
˙’
tro
.
.
c´o cho l`o
.
i gia
˙’
i cu
˙’
a b`ai to´an vˆe
`
c´ac
cˆo g´ai khˆong, ta lˆa
.

´
u c´o chung mˆo
.
t cˆo g´ai; nˆe
´
u sˇa
´
c sˆo
´
γ(G

) > 7 th`ı pha
˙’
i cho
.
n
tˆa
.
p ho
.
.
p kh´ac gˆo
`
m c´ac bˆo
.
ba cho nghiˆe
.
m cu
˙’
a b`ai to´an bˆo

n d¯ˆe
´
n l`o
.
i gia
˙’
i cu
˙’
a b`ai to´an vˆe
`
c´ac cˆo g´ai.
Nhˆa
.
n x´et 2.3.6 (a) Sˇa
´
c sˆo
´
γ(G) v`a sˆo
´
ˆo
˙’
n d¯i
.
nh trong α(G) liˆen hˆe
.
v´o
.
i nhau bˇa
`
ng bˆa

i c´ac
d¯ı
˙’
nh c`ung m`au v`a tu
.
o
.
ng ´u
.
ng ch´u
.
a n
1
, n
2
, . . . , n
γ
d¯ı
˙’
nh. Vˆa
.
y ta c´o
n = n
1
+ n
2
+ · · · + n
γ
≤ α(G) + α(G) + · · · + α(G) = γ(G).α(G).
(b) Ta c´o thˆe

´o
.
c hˆe
´
t d`ung m`au (1) d¯ˆe
˙’
tˆo tˆa
.
p ˆo
˙’
n d¯i
.
nh trong cu
.
.
c d¯a
.
i S
1
.
Rˆo
`
i d`ung m`au (2) d¯ˆe
˙’
tˆo tˆa
.
p ˆo
˙’
n d¯i
.

p ˆo
˙’
n d¯i
.
nh trong cu
.
.
c d¯a
.
i cu
˙’
a d¯ˆo
`
thi
.
con c`on la
.
i,
v.v. Thu
.
.
c ra khˆong pha
˙’
i nhu
.
vˆa
.
y. D
-
ˆo