Bài giảng về Lý thuyết đồ thị

Đ n đ th , đa đ th ồ ị

ồ ị

• Đ th ấ

ế ọ

ố ớ ỉ

đa đ thồ ị n u nó có ồ ị G = (V,E) g i là ít nh t m t c p đ nh đ c n i v i nhau ượ ộ ặ b i hai c nh tr lên và không có khuyên ạ ở ở

m ng này có nhi u kênh tho i n i gi a hai ạ ố

ạ ộ

ữ Ở ạ ề máy. Mô hình m ng trên là m t đa đ th . ồ ị

ồ

đ th ả ồ ị ng ậ

(không nh t thi

ứ ự t khác nhau)

ầ ử

ặ ấ

ế

ạ

c g i là khuyên n u có d ng

ế

ạ

ọ

Gi ướ G=(V,E) bao g m V là đ th vô h ả ồ ị t p các đ nh, E là t p các c p không có th t ỉ ậ g m hai ph n t ồ c a V g i là các c nh. ọ ủ • Các e đ ượ e=(u,u) • Ví d : ụ

ạ

ạ ừ ộ

ệ

ng đi n tho i t ộ

m t máy đ th ả ồ ị

M ng máy tính có đ ườ tính đ n chính nó. Mô hình trên là m t gi vô h

ng.

ế ướ

Đ th có h

ồ ị

ướ

G = (V,E) là đ th có h ng ồ ị

˛ ướ n u v i m i ọ ế các E có phân bi ứ ự ệ

ớ t th t ng x đ n y, hay ướ ế

c nh e=(x,y) ạ đ nh x và y, có h ỉ (x,y) „ (y,x)

y

ộ

ố ớ •

ầ

ố

•

ố ọ x và đ n y

ế

x Đ i v i m t cung e = (x, y): x là đ nh đi (g c,đ u) ỉ y là đ nh đ n(ng n, cu i) ế ỉ Cung e đi t ừ

Lý thuy t đ th ế ồ ị

Đ th có h

ng

ồ ị

ướ

Song song

Khuyên

G = (V, E)

V = {1, 2, 3, 4, 5, 6}

E = { (1,4), (1,6), (2,1), (2,3), (3,2), (4,3), (4,5), (4,6), (5,3), (6,1), (6,5),(5,3)}

(1, 4) = 1→4

Đ nh K

ỉ

ề

C nh K

ạ

ề

Lý thuy t đ th ế ồ ị

Đ th có h

ồ ị

ướ

• Cho G=(V,E) la môt đô thi co h ng va ́ ướ ̀ ̀ ̣ ̀ ̣

đinh sau

i c a vủ

c

̣ đinh tr

̀ ̉

j ướ cua v̉

i lân

ỉ ướ ̀ ̉ ̀

G G c ki hiêu la ́ ̣ ̀ • T p các đ nh sau va đinh tr (vi) va ̀ c c a v ủ -1(vi)

V | (x,y) ˛ E}

(x) = {y ˛ • G=(V,E) = (V, G )

Lý thuy t đ th ế ồ ị

e=(vi,vj)˛ E : c g i là – vj đ ọ ượ – vi la môt ậ t đ l ượ ượ G

Đ th có h

ồ ị

ướ

Lý thuy t đ th ế ồ ị

Đ th vô h

ồ ị

ướ

• G = (V,E) là đ th vô h ồ ị m i c nh e=(x,y) th t không k h

các đ nh x và y, t c là t ọ ạ ứ ự ướ n u v i ng ớ ế E không phân bi t ệ x đ n y ế ừ ỉ

ứ ng, hay (x,y) = (y,x) ể ướ

x

y

Lý thuy t đ th ế ồ ị

Đ th vô h

ng

ồ ị

ướ

G = (V, E)

V = {1, 2, 3, 4, 5}

E = {(1,2), (1,3), (1,4), (2,3), (3,5), (4,5)}

Lý thuy t đ th ế ồ ị

• c nh song song, khuyên? V | (x,y) ˛ E} • G ạ (x) = {y ˛

Đ th có tr ng s

ồ ị

ọ

ố

• Môt đô thi G = (V,E) goi la co trong l

ng hay trong sô

ượ

nêu môi canh(hoăc cung) đ

c gan 1 sô,

ượ

̣ ̀ ̣ ̣ ̀ ́ ̣ ̣ ́

: E R.

́ ̃ ̣ ̣ ́ ́

(e) goi la trong l

̣ w • nghia la co môt anh xa • Khi đó w

ượng cua e.

̃ ̀ ́ ̣ ́

̣ ̀ ̣ ̉

40

20

60

10

70

50

Lý thuy t đ th ế ồ ị

3.2. Các thu t ng c b n ữ ơ ả ậ K nhau

ề

• Cho G = (V,E) và e =(x,y) ˛

E là m t ộ

x và y. Khi đó ta nói e là

ỉ e. Khi đó x,y đ ộ x,y ho c ặ x,y là các đ nh ỉ hai c g i là ọ ượ

ỉ

n u gi a chúng có ữ ế

ỉ

ụ ớ c nh k nhau ề ạ

Lý thuy t đ th ế ồ ị

c nh n i đ nh ố ỉ ạ c nh ch a đ nh ứ ạ thu c c nh ạ đ nh k nhau ề • Hai c nh k nhau ề ạ đ nh chung. – Ví d v i u=(x,y) và v =(y,z) thì u,v là hai

Khái ni mệ

X2 và X3 là hai đỉnh kề nhau

X1 và X2 là hai đỉnh kề nhau

X1 và X4 là hai đỉnh kề nhau

Lý thuy t đ th ế ồ ị

B c c a đ nh ủ

ậ

ỉ ˛ V

(n a b c vào) = s các cung k t

ử

ế

ng ướ va v̀

ử thúc t

i (hay đi vào)

-1(vi) |

– n a bâc ngoai

ậ ố vi : deg- (vi)= | G ậ

̀ (n a b c ra) = s các cung kh i ở ố

• G=(V,E) có h – n a bâc trong ạ

đ u t (hay đi ra t )

ử ầ ừ

ử ừ vi : deg+ (vi)= | G

(vi) |

– bâc cua v

i : deg(vi) =deg- (vi) + deg+ (vi)

N a B c vào c a 1 là 3

ủ

ử

ậ

N a B c ra c a 1 là 1

ủ

ử

ậ

Lý thuy t đ th ế ồ ị

̣ ̉

B c c a đ nh

ậ ủ

ỉ

̀ ớ

ng ˛ V ướ va v̀ • G=(V,E) vô h

– bâc cua v

i i : deg(vi) = sô canh kê v i v

i, trong

̣ ̉ ́ ̣

̣ ́ ̀

đo ́ môt khuyên đ • Đ nh có b c = 0 đ ậ ỉ • Đ nh có b c = 1 đ ậ ỉ ớ ủ ạ

ậ

c đêm la 2 ượ c g i là đ nh cô l p ỉ ọ ượ c g i là đ nh treo và ọ ỉ ượ c g i là c nh i c a nó đ ọ ượ

ạ

Lý thuy t đ th ế ồ ị

cung (c nh) t treo

B c c a đ nh

ậ ủ

ỉ

Đ nh cô l p

ậ

ỉ

Đ nh treo

ỉ

C nh treo

ạ

d(a) = 1, d(b) = 4, d(c) = 4, d(d) = 1, d(e) = 3, d(f) = 3, d(g) = 0

Lý thuy t đ th ế ồ ị

B c c a đ nh

ậ ủ

ỉ

vi a b c d e

d-( vi) d+( vi) d( vi) 3 1 1 2 2

4 3 2 4 4

1 2 2 2 2

Lý thuy t đ th ế ồ ị

B c c a đ nh

ậ ủ

ỉ

Lý thuy t đ th ế ồ ị

B c c a đ nh

ậ ủ

ỉ

̉ ̀ ̣

ng thi

)

d v ( i

+ d v ( i

- ự – Nêu G co h • S liên hê gi a đinh va canh ̣ ữ ́ ướ ́ ̀ (cid:229) (cid:229)

v V i

)

= (cid:229)

d v ( i

˛ ˛

–

v V i

– Sô đinh bâc le la sô chăn

Lý thuy t đ th ế ồ ị

́ ̉ ̣ ̉ ̀ ́ ̃

3.3.M t s d ng đ th đ c bi

t ệ

ộ ố ạ Đ th đ (vô h ồ ị ủ

ồ ị ặ n ng) K ướ

• Là đ n ơ đ thồ ị câp n va gi a 2 đinh bât ky đêu co ̀ ữ

(m i đ nh c a đ th đ

c n i đ n t

ồ ị ượ

ủ

t c ố ế ấ ả

́ ̉ ́ ̀ ̀ ́

môt canh ỗ ỉ các đ nh khác trong đ th ) ồ ị

ỉ

n n - ( 2

ẽ

ạ

ng G goi la đu nêu đô thi vô

̣ ̣

ng ng cua no la đây đu

ướ

ươ

̣ ̀ ̣ ̣ ̀ ̉ ́ ̀ ̣

• M t đ th đ có n đ nh s có c nh ỉ ộ ồ ị ủ • Môt đô thi co h ́ ướ ng t ứ

̉ ́ ̀ ̀ ̉

̣ co h ̀ ̀

– Đô thi

˛ ng ́ ướ E  (y,x) ˛ ̀

̉ x ng : (x,y)

˛ ̀ ̣

c chiêu nhau

• Cho G=(V,E) la đô thi ̣ đ i x ng : (x,y) ố ứ Đô thi phan ứ – G la ̀ đ i x ng . Ta baỏ E E  (y,x) ˇ ố ứ đu nêu G đ n va gi a 2 đinh co 2 ̀ ữ ơ ̉ ́ ̉ ́

cung ng ượ G la phan ̉ x ngứ đu hay 1 vong thi đâu nêu G đ n va gi a 2 đinh co đung 1 cung. Ki hiêu T ̀ ữ

̀ ̉ ̀ ́ ́

́ ứ

̉ ́ ́ ́ ̣

– G la gia đôi x ng hay cân băng nêu d

eg-(vi) = deg+

(vi), " vi ˛

– G la k-đêu nêu G đ n va

̀ ̉ ̀ ́

ơ deg-(vi) = deg+(vi)=k, " vi ˛

̀ ̀ ́ ̀

ướ ̀ ̀ ̣ ̉

̀ eg(vi) =k,  " vi ˛

ộ ồ ị

ng. Ta bao V ̀ ̀ ́

v1, v2,…,vn và các c nh {

3, là m t đ th có v1, v2}, {v2, v3},

n đ nh ỉ …, {vn - 1, vn} và {vn, v1}

• Cho G=(V,E) la đô thi vô h – G la k-đêu nêu G đ n va d – Chu trình (vòng) Cn , v iớ n ‡ ạ

– G goi la môt banh xe nêu G co ́ :

̣ ̀ ̣ ́ ́

• n-1 đinh va ̀ n-1 canh ta • n-1 đinh cua no đêu nôi 1 đinh th n

tâm đa giac.

̣o thanh môt đa giac đêu ứ ở

̉ ̣ ̀ ̣ ́ ̀

̉ ̉ ́ ̀ ́ ̉ ́

– Ki hiêu W n

́ ̣

Đ th l

ng phân

ồ ị ưỡ

̣ ́ ́ ̉ ̣

ng phân nêu V co thê phân hoach ̀ ưỡ 1, V2 sao cho moi canh cua G đêu nôi 1

– G goi la l thanh V đinh trong

ớ

̀ ̣ ̣ ̉ ̀ ́

V1 v i môt đinh trong

̉ ̣ ̉

Đ th l

ng phân

ồ ị ưỡ

̀ ọi đinh trong V

̣ ưỡ

́ ̉ ̀ ́ ̉

́ ̉ ̀ ̣ ̀ ̀

2 thi G goi la đô thi l n,m v i n=| ớ

V1| va m=|

1 đêu nôi v i tât ca ́ ớ ng phân V2|. Đăc biêt K

1,m

• Nêu G đ n va m ơ cac đinh trong V đu, ̉ ký hi u Kệ goi la đô thi ngôi sao

̀ ̣ ̣

Lý thuy t đ th ế ồ ị

̣ ̀ ̀ ̣

Đ th l

ng phân

ồ ị ưỡ

Đ th G là phân đôi, v i {

ồ ị

ớ a, b, d} và {c, e, f, g}.

ồ ị

t c các đ nh khác; do đó V1 = {

ố ớ ấ ả

Đ th H là không phân đôi, vì - f n i v i t - a và b l

ỉ i n i v i nhau .

ạ ố ớ

Lý thuy t đ th ế ồ ị

Đ th con

ồ ị

ỏ ế

ạ ủ c g i là ọ đ ồ

• N u trong đ th ta b đi m t s đ nh ồ ị ộ ố ỉ nào đó và các c nh ch a đ nh đó thì ỉ ứ ạ i c a đ th đ ph n còn l ồ ị ượ ầ c a đ th đã cho. th con ồ ị ủ ị • N u trong đ th ta b đi m t s c nh ế ộ ố ạ gi nguyên các đ nh thì ph n còn l i ạ ữ ầ ỉ ậ đ th b ph n c a đ th đ c g i là ồ ị ộ ọ ủ c a đ th đã cho. ủ

ồ ị ỏ

Lý thuy t đ th ế ồ ị

ồ ị ượ ồ ị

Ví dụ

H=(U,F)

G=(V,E)

Lý thuy t đ th ế ồ ị

Đô thi con • Cho G = (V,E) va G’ = (V’,E’) la 2 đô thi cung co

̀ ̣

ng hoăc cung không co h

́ ướ

̀ ̀ ̀ ̣ ̀ ́

c goi la đô thi con cua G, ki hiêu

̣ G’ £

̣ ̀

V, E’ ˝

h ướ – G’ đ nêu

E va (v̀

i,vj) ˛

E’  vi, vj ˛ V’

̣ ̀ ̀ ̣ ̉ ́

G v i V’=V thi G’ goi la

ượ ́ V’ ˝ – Nêu G’

ớ

̀ đô thi bô phân

hay đô thi khung

cua G.

£ ́ ̀ ̣ ̀ ̣ ̣ ̣

̀ ̣ ̉

– Nêu V’=V va E’=E – {e}, e

E thi G’ đ

c viêt la

ượ

G – e

˛ ́ ̀ ̀ ́ ̀

Đ th bù ồ ị

• Cho Kn = (V, E) va G = (V, E

1) la đô thi khung cua

̀ đô thi

̀ ̀ ̀ ̣ ̉

Kn G • Đăt ̣ = (V, E2) v i Eớ

2 = E – E1 thì goi la

bu ̀ cua G̉

1 ˙ • Kn = (V, E1 ¨ E2) va È

E2 = ˘

̣ ̀ ̣

Đăng câu(đăng hinh) đô thi • Hai đô thi G = (V,E) va G’ = (V’,E’) goi la đăng

̉ ́ ̉ ̀ ̀ ̣

ớ

̀ ̣ ̀ ̣ ̀ ̉

: câu v i nhau nêu – co môt phep t ng ng 1 – 1(song anh) gi a 2 ́ ươ

ữ

ứ

́ ́

tập V, V’

– va co môt phep t

ng ng 1 – 1 gi a 2 tâp h p

́ ươ

ữ

ứ

ợ

́ ̣ ́

E, E’ Sao cho:

e = (v,w) ˛

ươ

̀ ́ ̣ ̣

́ ̣ ̣

E t ứ E’ thi căp đinh v, w

ng ng v i canh ớ V cung la

˛ ̀ ̣ ̉ ̃ ̀

nêu canh e’ = (v’,w’) ˛ t ươ

ứ

ng ng cua căp đinh v’, w’ j • G, G’ đăng câu nêu tôn tai môt song anh

˛ ̉ ̣ ̉

VV’ sao cho: (i, j) ˛

E (j (i), j (j)) ˛

E’.

̉ ́ ́ ̀ ̣ ̣ ́

Đăng câu(đăng hinh) đô thi

̉ ́ ̉ ̀ ̀ ̣

j • Nêu G, G’ la đăng câu qua anh xa thi hai ́ ̀ ̉ ́ ́ ̣ ̀

ứ

̀ ̣

́ ̀ ́ ̉ ̀

́ ̀ ́ ̣

́ ̀ ́ ̉ ̣ ̃

V va ̀

̀ ớ

V’ la nh ư

nhau.

j đô thi: – Co cung sô đinh, t c la |V| = |V’| – Co cung sô canh: |E| = |E’| – Co cung sô đinh v i bâc cho săn ớ (i) ˛ ˛ – Sô đinh kê v i đinh i ́ ̉ ̉ ̀

Ví dụ

ớ

ỏ

1) = v1, f(u2) = v4 , f(u3) = v3, f(u4) = v2 thì G,H là

đ ng c u

V i ánh x f th a f(u ạ ấ

ẳ

ng đi,

ườ

ề chu trình, m ch. Đ th liên thông

3.4. Dây chuy n, đ ạ

ồ ị

• Dây chuy n trong m t đ th không có đ nh h

ộ ồ ị

ề

ị

ng: ạ , sao cho m i m t c nh

ướ ộ ạ

ỗ

ế

ộ ỉ

ế

• Chu trình: dây chuy n có đ nh kh i đ u và đ nh k t

m t ộ dãy liên ti p các c nh có m t đ nh chung v i c nh ti p theo. ớ ạ ở ầ ề

ỉ

ế

ỉ

nao xuât hiên

thúc trùng nhau • Dây chuyên s câp ơ

: không co ́ đinh̉

qua ḿ ột lâǹ • Dây chuyên đ n

nao xuât hiên qua

ơ : không co ́ canḥ

̀ ́ ̀ ́ ̣

1 l nầ

́ ?

̀ ̀ ́ ̣ ́

ườ

• chu trinh đ n va chu trinh s câp • Đ ng và m ch là khái ni m dây chuy n và chu

trình trong tr

ệ ng h p đ th có đ nh h ồ ị

ạ ườ

ề ướ

ợ

ị

̀ ̀ ̀

Ví dụ

Từ B đến D

(B,A),(A,D) =B, A, D

B, C, D

Lý thuy t đ th ế ồ ị

Ví dụ

3,2,1,4,5,3

Lý thuy t đ th ế ồ ị

Chu trình Halmilton

1,4,5,3,2,1

Lý thuy t đ th ế ồ ị

Đ th vô h

ng liên thông

ồ ị

ướ

• Đ th vô h ồ ị

ọ ng đi gi a hai đ nh b t kỳ

c g i là liên thông

c đ

ng G = (V, E) đ ườ ượ

ượ ữ

ấ

ỉ

ướ n u ế luôn tìm đ c a nó. ủ

• Trên V ta đinh nghia quan hê t

ng đ

̣ ươ

ươ

ng ~ nh ư

̣ ̃

́ x ~ y thi ta noi

̀ ́ ̀

́ ớ ươ

ươ

̣ ̃ ̀

x ~ y  x = y hay co ḿ ột dây chuyên nôi x va y ́ x liên thông v i yớ Nêu Quan hê ~ se phân G thanh cac l p t goi la cac thanh phân liên thông. ng Nêu G chi co 1 thanh phân liên thông thi G liên

̣ ̀ ́ ̀ ̀

thông

́ ̉ ́ ̀ ̀ ̀

Ví dụ

Đ th vô h

ng liên thông

ướ

ồ ị • Cho đ th vô h

ồ ị ướ

liên thông

ng G = (V, E) liên thông – Đinh i goi la điêm kh p cua G nêu G-i không ớ ̉ ̣ ̀ ̉ ̉ ́

E goi la câu nêu G-e không liên

– Canh e thông

cua G, ki hiêu la e(G) la sô

– Sô ́ liên thông canh

˛ ̣ ̣ ̀ ̀ ́

̣ ̉ ́ ̣ ̀ ̀ ́

canh it nhât xoa đi G không con liên thông đ nh xem nh không liên thông)

ỉ

cua G, ki hiêu la v(G) la sô

– Sô ́ liên thông đinh

̣ ́ ́ ́ ̀

đinh it nhât xoa đi G không con liên thông

̉ ̉ ́ ̣ ̀ ̀ ́

̉ ́ ́ ́ ̀

Ví dụ

ng liên thông m nh

Đ th h u h ồ ị ữ

ướ

ạ

c g i là ọ

ồ ị có h

ướ n u luôn tìm đ

c đ

ượ ng đi gi a hai đ nh

ng G = (V, E) đ ườ ượ

liên thông ỉ

ữ

• Đ th manḥ b t kỳ c a nó ấ

ế ủ

• Trên V ta đinh nghia quan hê t

ng đ

̣ ươ

ươ

ng ~ nh ư

ng đi t

x đên y va

̣ ườ

ừ

̣ ̃

y đên x

ng đi t

co môt đ

x ~ y  x = y hay co môt đ ừ

̣ ườ

́ ́ ̀

́ ́

Nêu x ~ y thi ta noi x liên thông manh v i y Quan hê ~ se phân G thanh cac l p t

ớ ng goi la ́ ớ ươ

́ ̀ ́ ̣

cac thanh phân liên thông manh.

̣ ̃ ̀ ̣ ̀

Nêu G chi co 1 thanh phân liên thông manh thi G

́ ̀ ̀ ̣

liên thông manḥ

́ ̉ ́ ̀ ̀ ̣ ̀

ng liên thông m nh

Đ th h u h ồ ị ữ

ướ

ạ

• Đ th có h ồ ị

ng ướ ế c g i là ọ ng t ươ

ế ng v i nó là vô h ượ ướ ồ ị ng liên thông ng G = (V, E) đ liên thông y u n u đ th vô h ứ ướ ớ

Ch

ươ

ng 4: Bi u di n đ th ồ ị

ễ ể trên máy tính

Lý thuy t đ th ế ồ ị

N i dung

ộ

4.14.1

ế ỉ

ể

ễ

ằ

ạ

Bi u di n b ng ma tr n liên k t đ nh c nh ậ

4.24.2

4.34.3

ể ễ Bi u di n hình h c ọ

4.44.4

ể ễ ậ ề Bi u di n b ng ma tr n k ằ

ể ễ ề Bi u di n b ng danh sách k ằ

Bi u di n hình h c ọ

ễ

ể

˛ ớ ứ ng ng v i m i ỗ

1. M i đ nh v ỗ ỉ ể ớ ườ

˛ ướ ng h p này n u e =(x,y)

ợ ặ

V ta đ t t ặ ươ đi m trên m t m t ph ng. ẳ ặ ộ ng. Trong 2. V i G =(V,E) là đ th có h ồ ị E thì tr ế trong m t ph ng s có m t cung có ẽ h ộ ỉ

ộ

Lý thuy t đ th ế ồ ị

ẳ ng đi t ừ ỉ ướ ˛ 3. N u (x,x) ế khuyên có h đ nh x đ n đ nh y ế i đ nh x s có m t E thì t ẽ ạ ỉ ng vào chính nó ướ

Bi u di n hình h c ọ

ể

ễ

Lý thuy t đ th ế ồ ị

Ma tr n liên k t đ nh c nh

ế ỉ

ậ

ạ

– V = {v1,v2,…,vn} – E = {e1,e2,…,em} • Ma tr n liên k t

• Cho G=(V,E)

ế đ nh c nh c a G là ma ủ

Lý thuy t đ th ế ồ ị

ậ tr n A = (a ậ ạ ỉ ở : ij)n×m đ nh b i ị

Ma tr n liên k t đ nh c nh

ế ỉ

ạ

ậ

– N u G vô h

ế

ướ

– G có h

ngướ

Lý thuy t đ th ế ồ ị

Ví dụ

Lý thuy t đ th ế ồ ị

Ví dụ

e1 e2 e3 e4 e5 e6 e7 e8 v1 2 1 1 0 0 0 0 0 v2 0 1 1 1 0 1 1 0 v3 0 0 0 1 1 0 0 0 v4 0 0 0 0 0 0 1 2 v5 0 0 0 0 1 1 0 0

Lý thuy t đ th ế ồ ị

Ví dụ

Lý thuy t đ th ế ồ ị

Ví dụ

Lý thuy t đ th ế ồ ị

Ví dụ

Lý thuy t đ th ế ồ ị

Ví dụ

Lý thuy t đ th ế ồ ị

Ma tr n kậ

ề

– V = {v1,v2,…,vn} – E = {e1,e2,…,em}

• Cho G=(V,E)

ij)n×n

ủ ậ • Ma tr n ậ k ề c a G là ma tr n A = (a

Lý thuy t đ th ế ồ ị

ở : đ nh b i ị

Ma tr n kậ

ề

– N u G vô h

ế

ướ

– G có h

ngướ

Lý thuy t đ th ế ồ ị

Bi u di n b ng ma tr n k ằ

ễ

ể

ậ

ề

0 1 0 0

1 0 1 2

0 1 0 0

0 2 0 0

Lý thuy t đ th ế ồ ị

Ví dụ

Lý thuy t đ th ế ồ ị

Ví dụ

Lý thuy t đ th ế ồ ị

Ví dụ

Lý thuy t đ th ế ồ ị

Ví dụ

Lý thuy t đ th ế ồ ị

ng đi gi a các đ nh

Đ m đ ế

ườ

ữ

ỉ

• Cho G là m t đ th v i ma tr n li n k A ậ ề

ứ ự

ướ

ườ ộ

v ừ i ng, ươ (i, j) c a ma tr n ậ ầ ử ị ủ ủ

Lý thuy t đ th ế ồ ị

ề ộ ồ ị ớ các đ nh v1, v2 ,…, vn (v i theo th t ớ ỉ các c nh vô h ng ho c có h ng hay là ướ ặ ạ c nh b i, có th có khuyên). ể ộ ạ ng đi khác nhau đ dài r t • S các đ ố i vớ j , trong đó r là m t s nguyên d t ộ ố b ng giá tr c a ph n t ằ Ar .

ng đi gi a các đ nh

Đ m đ ế

ườ

ữ

ỉ

a t i d ườ ng đi đ dài 4 t ộ ừ ớ

0 1 1 0 A = 1 0 0 1 1 0 0 1 0 1 1 0

Đ th G ồ ị

8 0 0 8 A4 = 0 8 8 0 0 8 8 0 8 0 0 8

Lý thuy t đ th ế ồ ị

• Có bao nhiêu đ trong đ th đ n G? ồ ị ơ

Danh sách kề

ề ể

ng: li ệ ướ

• Dùng danh sách li n k đ mô t t kê t ủ ng: li ướ

ỉ m i đ nh t c các đ nh ừ ỗ ỉ t kê t ấ

Lý thuy t đ th ế ồ ị

đ th ề ả ồ ị t c các đ nh li n k vô h ề ề ỉ ấ ả v i m i đ nh c a đ th ỗ ỉ ồ ị ớ • Đ th có h ấ ả ệ ồ ị cu i c a các cung xu t phát t ố ủ c a đ th ồ ị ủ

Ví dụ

Lý thuy t đ th ế ồ ị

Ví dụ

Lý thuy t đ th ế ồ ị

Danh sách kề