Đồ thị: Các số cơ bản và thuật toán liên quan

http://www.ebook.edu.vn

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

.thuˆo

.c v`ao su

.

.d¯i

.nh hu

.´o

.ng: ta s˜e n´oi vˆe

`

ca

.nh ch´u

.khˆong pha

˙’icung. D

-ˆe

˙’ tˆo

˙’ng qu´at x´et d¯a d¯ˆo

`thi

.vˆo hu

.´o

.ng G:= (V, E) c´o nd¯ı

˙’nh, m

ca

.nh v`a pth`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

-i

.nh l´y 2.1.1 Cho d¯a d¯ˆo

`thi

.vˆo hu

.´o.ng G= (V, E).Gia

˙’ su

.

˙’ G′l`a d¯ˆo

`thi

.nhˆa

.n d¯u

.o.

.c t`u

.G

bˇa

`ng c´ach nˆo

´i hai d¯ı

˙’nh av`a bcu

˙’aGbo.

˙’ i mˆo

.t ca

.nh m´o.i; nˆe

´uav`a btr`ung nhau hoˇa

.c c´o thˆe

˙’

nˆo

´i v´o.i nhau bo.

˙’ i mˆo

.t dˆay chuyˆe

`n cu

˙’aGth`ı

ρ(G′) = ρ(G), ν(G′) = ν(G) + 1;

trong tru

.`o.ng ho.

.p ngu

.o.

.c la

.i

ρ(G′) = ρ(G) + 1, ν(G′) = ν(G).

Ch´u

.ng minh. Theo c´ach xˆay du

.

.ng, d¯a d¯ˆo

`thi

.G′c´o n′=nd¯ı

˙’nh, m′=m+ 1 ca

.nh v`a gia

˙’ su

.

˙’

G′c´o p′th`anh phˆa

`n liˆen thˆong.

Nˆe

´ua≡bhoˇa

.c c´o mˆo

.t dˆay chuyˆe

`n nˆo

´iav´o

.ib. Khi d¯´o ph´ep biˆe

´n d¯ˆo

˙’iGth`anh G′

khˆong thay d¯ˆo

˙’i sˆo

´th`anh phˆa

`n liˆen thˆong, t´u

.c l`a p=p′.Do d¯´o

ρ(G′) = n′−p′=n−p=ρ(G),

ν(G′) = m′−ρ(G′) = ν(G) + 1.

49

http://www.ebook.edu.vn

Ngu

.o.

.c la

.i, nˆe

´ua6=bv`a khˆong tˆo

`n ta

.i dˆay chuyˆe

`n nˆo

´iav`a b, th`ı do c´ach x´ac d¯i

.nh G′

ta c´o p′=p−1.Suy ra

ρ(G′) = n′−p′=n−(p−1) = n−p+ 1 = ρ(G)+1,

ν(G′) = m′−ρ(G′) = (m+ 1) −(ρ(G) + 1) = m−ρ(G) = ν(G).

⊳

Hˆe

.qua

˙’ 2.1.2 ρ(G)≥0v`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

hu

.´o

.ng G, d¯ı

˙’nh no

.cˆo lˆa

.p v´o

.i d¯ı

˙’nh kia, ta xˆay du

.

.ng G′dˆa

`n dˆa

`n t`u

.ng ca

.nh mˆo

.t; kho.

˙’ 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

.G′,c´ac sˆo

´ρv`a νchı

˙’ c´o

thˆe

˙’ tˇang. ⊳

D

-ˆe

˙’ c´o thˆe

˙’ vˆa

.n du

.ng nh˜u

.ng kˆe

´t qua

˙’ phong ph´u cu

˙’a d¯a

.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 Gv´o

.i mˆo

.t vector theo c´ach sau d¯ˆay.

Mˆo

˜i ca

.nh cu

˙’a d¯a d¯ˆo

`thi

.Gd¯ˆe

`u d¯u

.o.

.c d¯i

.nh hu

.´o

.ng mˆo

.t c´ach t`uy ´y; nˆe

´u chu tr`ınh µd¯i

qua ca

.nh ek, rklˆa

`n thuˆa

.n hu

.´o

.ng v`a sklˆa

`n ngu

.o

.

.c hu

.´o

.ng th`ı ta d¯ˇa

.tck:= rk−sk(nˆe

´uekl`a

mˆo

.t khuyˆen th`ı ta luˆon qui u

.´o

.csk= 0).Vector mchiˆe

`u

(c1, c2, . . . , cm)

go

.i l`a vector chu tr`ınh tu

.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

.pnˆe

´u c´ac vector chu tr`ınh tu

.o.ng ´u

.ng d¯ˆo

.c lˆa

.p

tuyˆe

´n t´ınh. Ch´u ´y rˇa

`ng, d¯i

.nh ngh˜ıa n`ay khˆong phu

.thuˆo

.c v`ao hu

.´o

.ng g´an cho c´ac ca

.nh.

D

-i

.nh l´y 2.1.3 Chu sˆo

´ν(G)cu

˙’aG= (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

˙’ 2.1.2: d¯ˆa

`u tiˆen ta lˆa

´y d¯ˆo

`thi

.vˆo hu

.´o

.ng khˆong

c´o ca

.nh v´o.i tˆa

.p c´ac d¯ı

˙’nh l`a V. Sau d¯´o ta xˆay du

.

.ng d¯a d¯ˆo

`thi

.G′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

.i, chu sˆo

´khˆong thay d¯ˆo

˙’i trong tru

.`o

.ng ho.

.p ngu

.o.

.c la

.i.

Gia

˙’ su

.

˙’ , tru

.´o

.c khi thˆem ca

.nh ekta 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 ekxuˆa

´t hiˆe

.n thˆem c´ac chu tr`ınh so.cˆa

´p m´o

.iγ1, γ2, . . . ,

n`ao d¯´o. Hiˆe

˙’n nhiˆen γ1khˆong thˆe

˙’ biˆe

˙’u diˆe

˜n tuyˆe

´n t´ınh qua hˆe

.c´ac chu tr`ınh µj(v`ı c´ac vector

50

http://www.ebook.edu.vn

tu

.o.ng ´u

.ng c´ac chu tr`ınh µjc´o th`anh phˆa

`n th´u

.kbˇa

`ng khˆong, trong khi vector tu

.o.ng ´u

.ng

chu tr`ınh γ1c´o th`anh phˆa

`n th´u

.kkh´ac khˆong). Mˇa

.t kh´ac c´ac vector γ2, γ3, . . . c´o thˆe

˙’ biˆe

˙’u

diˆe

˜n tuyˆe

´n t´ınh qua γ1, µ1, µ2, µ3, . . . . T´om la

.i mˆo

˜i khi chu sˆo

´tˇang mˆo

.t d¯o

.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.

.c ch´u

.ng minh.

⊳

T`u

.kˆe

´t qua

˙’ n`ay, dˆe

˜d`ang suy ra:

Hˆe

.qua

˙’ 2.1.4 (a) D

-a d¯ˆo

`thi

.vˆo hu

.´o.ng Gkhˆong c´o chu tr`ınh nˆe

´u v`a chı

˙’ nˆe

´uν(G) = 0.

(b) D

-a d¯ˆo

`thi

.vˆo hu

.´o.ng Gc´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

`thi

.c´o hu

.´o.ng liˆen thˆong ma

.nh, chu sˆo

´bˇa

`ng sˆo

´cu

.

.c d¯a

.i c´ac ma

.ch

d¯ˆo

.c lˆa

.p tuyˆe

´n t´ınh.

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

˙’aG(mˆo

˜i cung

tu

.o.ng ´u

.ng mˆo

.t cˇa

.p ca

.nh) v`a mˆo

.t chu tr`ınh so.cˆa

´pµ; ta phˆan hoa

.ch tˆa

.p c´ac d¯ı

˙’nh trˆen chu

tr`ınh n`ay th`anh: tˆa

.pSc´ac d¯ı

˙’nh c´o mˆo

.t cung t´o.i n´o v`a mˆo

.t cung ra kho

˙’i n´o, tˆa

.pS′c´ac d¯ı

˙’nh

c´o hai cung cu

˙’aµra kho

˙’i n´o v`a tˆa

.pS′′ 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

.i nˆen #S′= #S′′; gia

˙’ su

.

˙’ v′

1, v′

2, . . . , v′

kl`a c´ac phˆa

`n tu

.

˙’ cu

˙’aS′v`a

v′′

1, v′′

2, . . . , v′′

kl`a c´ac phˆa

`n tu

.

˙’ cu

˙’aS′′.

Trˆen chu tr`ınh µ, c´ac phˆa

`n tu

.

˙’ cu

˙’aS′v`a cu

˙’aS′′ xen k˜e nhau v`a ta gia

˙’ su

.

˙’ rˇa

`ng sau d¯ı

˙’nh

v′

ith`ı d¯ı

˙’nh d¯ˆa

`u tiˆen bˇa

´t gˇa

.p (khˆong thuˆo

.cS) l`a v′′

i; cuˆo

´i c`ung, nˆe

´uµ0l`a mˆo

.t d¯u

.`o

.ng d¯i gˇa

.p

d¯ı

˙’nh xtru

.´o

.c d¯ı

˙’nh yth`ı ta k´y hiˆe

.uµ0[x, y] l`a d¯u

.`o

.ng d¯i bˆo

.phˆa

.n cu

˙’aµ0t`u

.xd¯ˆe

´ny. V`ı d¯ˆo

`

thi

.liˆen thˆong ma

.nh nˆen tˆo

`n ta

.i ma

.ch µ1d¯i qua v′

i+1 v`a v′′

iv`a d`ung c´ac cung cu

˙’aµd¯ˆe

˙’ d¯i t`u

.

v′

i+1 d¯ˆe

´nv′′

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

´t

µ=µ[v′

1, v′′

1]−µ1[v′

2, v′′

1] + µ[v′

2, v′′

2] + · · ·

=µ[v′

1, v′′

1] + µ1[v′′

1, v′

2] + µ[v′

2, v′′

2] + µ2[v′′

2, v′

3] + · · · − (µ1+µ2+· · ·).

Vˆa

.y mo

.i chu tr`ınh so.cˆa

´p d¯ˆe

`u l`a tˆo

˙’ ho.

.p tuyˆe

´n t´ınh cu

˙’a c´ac ma

.ch, d¯ˆo

´i v´o

.i c´ac chu tr`ınh

bˆa

´t k`y d¯iˆe

`u d¯´o c˜ung d¯´ung (v`ı n´o l`a tˆo

˙’ ho.

.p tuyˆe

´n t´ınh cu

˙’a c´ac chu tr`ınh so.cˆa

´p).

Trong Rm,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

-i

.nh l´y 2.1.3 th`ı co

.so.

˙’ n`ay c´o sˆo

´chiˆe

`u l`a ν(G).Vˆa

.y sˆo

´cu

.

.c d¯a

.i c´ac ma

.ch d¯ˆo

.c

lˆa

.p tuyˆe

´n t´ınh bˇa

`ng ν(G). ⊳

51

http://www.ebook.edu.vn

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 Gv´o

.ind¯ı

˙’nh, v`a cˆa

`n tˆo m`au c´ac d¯ı

˙’nh sao

cho hai d¯ı

˙’nh kˆe

`nhau c´o m`au kh´ac nhau. Hiˆe

˙’n nhiˆen l`a c´o thˆe

˙’ d`ung nm`au d¯ˆe

˙’ tˆo c´ac d¯ı

˙’nh

d¯´o, nhu

.ng nhu

.thˆe

´vˆa

´n d¯ˆe

`d¯ˇa

.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

.p kh´ac nhau-mˆo

.t tˆa

.p gˆo

`m c´ac d¯ı

˙’nh d¯u

.o.

.c tˆo m`au d¯o

˙’, mˆo

.t tˆa

.p c´ac

d¯ı

˙’nh d¯u

.o.

.c tˆo m`au xanh, vˆan vˆan. D

-ˆ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

.m ch´ı c´o thˆe

˙’ quan tˆam d¯ˆe

´n viˆe

.c tˆo m`au c´ac diˆe

.n.

Trong phˆa

`n n`ay ta chı

˙’ x´et c´ac d¯ˆo

`thi

.vˆo hu

.´o

.ng liˆen thˆong.

D

-i

.nh ngh˜ıa 2.2.1 Cho tru

.´o

.c mˆo

.t sˆo

´nguyˆen p, ta n´oi rˇa

`ng d¯ˆo

`thi

.Gl`a p−sˇa

´cnˆ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

´pnho

˙’ nhˆa

´t, m`a d¯ˆo

´i v´o.i sˆo

´d¯´o Gl`a p−sˇa

´c go

.i l`a sˇa

´c sˆo

´cu

˙’a d¯ˆo

`thi

.Gv`a k´y hiˆe

.u l`a γ(G).

V´ı du

.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

•

.

..

.

..

.

..

.

..

.

g y

p

• •

•

(a)

g y

r

• •

•

(b)

r r

b

• •

•

(c)

H`ınh 2.1:

V´ı du

.2.2.3 Ba

˙’n d¯ˆo

`d¯i

.a l´y. Ta v˜e trˆen mˇa

.t phˇa

˙’ng mˆo

.t ba

˙’n d¯ˆo

`. Go

.iVl`a tˆa

.p ho.

.p c´ac

nu

.´o

.c, d¯ˇa

.t (i, j)∈Enˆe

´u c´ac nu

.´o

.civ`a jc´o biˆen gi´o

.i chung. D

-ˆo

`thi

.G= (V, E) d¯ˆo

´i x´u

.ng

v`a c´o t´ınh chˆa

´t rˆa

´t d¯ˇa

.c biˆe

.t l`a: c´o thˆe

˙’ v˜e n´o lˆen mˇa

.t phˇa

˙’ng m`a khˆong c´o hai ca

.nh n`ao cˇa

´t

nhau (tr`u

.ta

.i c´ac d¯ı

˙’nh chung); n´oi c´ach kh´ac, Gl`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

.phˇa

˙’ng d¯ˆe

`u nho

˙’ ho.n hoˇa

.c bˇa

`ng bˆo

´n (D

-i

.nh l´y 6.4.7). Nhu

.vˆa

.y bˇa

`ng bˆo

´n

m`au c˜ung d¯u

˙’ d¯ˆe

˙’ 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

http://www.ebook.edu.vn

T`u

.d¯i

.nh ngh˜ıa dˆe

˜d`ang suy ra

1. Mˆo

.t d¯ˆo

`thi

.chı

˙’ c´o c´ac d¯ı

˙’nh cˆo lˆa

.p l`a 1−sˇa

´c.

2. Mˆo

.t d¯ˆo

`thi

.c´o mˆo

.t hoˇa

.c hai ca

.nh (khˆong pha

˙’i l`a mˆo

.t khuyˆen) c´o sˇa

´c sˆo

´´ıt nhˆa

´t bˇa

`ng

hai.

3. D

-ˆo

`thi

.d¯ˆa

`y d¯u

˙’ nd¯ı

˙’nh Knl`a n−sˇa

´c.

4. D

-ˆo

`thi

.l`a mˆo

.t chu tr`ınh d¯o

.n gia

˙’n v´o

.ind¯ı

˙’nh, n > 3,l`a 2−sˇa

´c nˆe

´unchˇa

˜n v`a 3−sˇa

´c

nˆe

´unle

˙’.

5. Hiˆe

˙’n nhiˆen, mo

.i d¯ˆo

`thi

.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

Vth`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

.

., d¯ˆo

`thi

.hai phˆa

`n l`a

2−sˇa

´c, v´o

.i mˆo

.t tru

.`o

.ng ho.

.p ngoa

.i lˆe

.tˆa

`m thu

.`o

.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

.isˇa

´c l´o

.pcu

˙’a d¯ˆo

`thi

.Gl`a sˆo

´nguyˆen qc´o c´ac t´ınh chˆa

´t sau:

1. C´o thˆe

˙’ d`ung qm`au kh´ac nhau d¯ˆe

˙’ tˆo m`au c´ac ca

.nh cu

˙’aGsao cho hai ca

.nh kˆe

`nhau

khˆong c`ung mˆo

.t m`au;

2. D

-iˆe

`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

˙’a d¯ˆo

`thi

.G′= (V′, E′)

d¯u

.o.

.c x´ac d¯i

.nh nhu

.sau: mˆo

˜i d¯ı

˙’nh cu

˙’aG′tu

.o.ng ´u

.ng mˆo

.t ca

.nh cu

˙’aG; ca

.nh e′= (v′

1, v′

2)∈E′

nˆe

´u c´ac ca

.nh e1v`a e2(tu

.o.ng ´u

.ng v´o

.i hai d¯ı

˙’nh v′

1, v′

2) kˆe

`nhau.

Nhu

.vˆa

.y b`ai to´an sˇa

´c l´o.p d¯u

.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

.nh l´y 2.2.5 [K¨onig] D

-ˆo

`thi

.vˆo hu

.´o.ng Gl`a 2−sˇa

´c nˆe

´u v`a chı

˙’ nˆe

´u n´o khˆong c´o chu tr`ınh

c´o d¯ˆo

.d`ai le

˙’.

Ch´u

.ng minh D

-iˆe

`u kiˆe

.n cˆa

`n. Nˆe

´u d¯ˆo

`thi

.Gl`a 2−sˇa

´c, th`ı tˆa

´t nhiˆen Gkhˆ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

.i nhu

.vˆa

.y khˆong thˆe

˙’ tˆo bˇa

`ng hai m`au

theo nhu

.quy tˇa

´c d¯˜a chı

˙’ ra o.

˙’ trˆen.

D

-iˆe

`u kiˆe

.n d¯u

˙’.Gia

˙’ su

.

˙’ d¯ˆo

`thi

.Gkhˆ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 Gl`a liˆen thˆong. Ta s˜e tˆo m`au dˆa

`n c´ac d¯ı

˙’nh cu

˙’aGtheo quy tˇa

´c

sau:

53

Đồ thị và các thuật toán – Chương 2: Các số cơ bản của đồ thị

Chủ đề:

Tài liệu liên quan

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi