Tài liệu Đại cương về vẽ đồ thị

??I C??NG V? ?? TH?

I. C￁C KH￁I NI?M C? B?N
1. ?? th?
2. Bi?u di?n ?? th?
3. B?c c?a ??nh trong ?? th?
4. Ch?ng minh - gi?i b￠i to￡n b?ng ph??ng ph￡p ?? th?
II. M?T S? ?? TH? ??C BI?T
1. ?? th? ??y ??
2. ?? th? v￲ng
3. ?? th? h￬nh b￡nh xe
4. ?? th? ??u
5. C￡c kh?i n-l?p ph??ng
6. ?? th? b
7. ?? th? l??ng ph￢n
III. S? ??NG C?U C?A C￁C ?? TH?
1. ??nh ngh?a
2. ?? th? t? b
IV. ?? TH? Cￓ H??NG
1. ??nh ngh?a
2. B?c c?a ??nh trong ?? th? c￳ h??ng
V. TￍNH LIￊN THￔNG
1. ???ng ?i
2. Chu tr￬nh
3. T￭nh li￪n th￴ng trong ?? th? v￴ h??ng
4. T￭nh li￪n th￴ng trong ?? th? c￳ h??ng
VI. M?T S? PH￉P BI?N ??I ?? TH?
1. H?p c?a hai ?? th?
2. Ph￩p ph￢n chia s? c?p

I. C￡c kh￡i ni?m c? b?n TOP



1. ?? th? TOP


?? th? (graph) G = (V,E) l￠ m?t b? g?m 2 t?p h?p V v￠ E, trong ?￳ V ﾹ ￆ c￡c ph?n t? c?a V ???c g?i l￠ c￡c ??nh (vertices), c￡c ph?n t? c?a E ???c g?i l￠ c￡c c?nh (edges), m?i c?nh t??ng ?ng v?i 2 ??nh.
N?u c?nh e t??ng ?ng v?i 2 ??nh v, w th￬ ta n￳i v v￠ w l￠ 2 ??nh k? (hay 2 ??nh li￪n k?t) (adjacent) v?i nhau. Ta c?ng n￳i c?nh e t?i hay li￪n thu?c (incident) v?i c￡c ??nh v v￠ w. K hi?u e = hay v w (ho?c e = vw; e = wv). C?nh t??ng ?ng v?i 2 ??nh trng nhau g?i l￠ m?t v￲ng hay khuy￪n (loop) t?i v.
Hai c?nh ph￢n bi?t cng t??ng ?ng v?i m?t c?p ??nh ???c g?i l￠ 2 c?nh song song (paralleledges) hay c?nh b?i. ?? th? kh￴ng c￳ c?nh song song v￠ c?ng kh￴ng c￳ v￲ng ???c g?i l￠ ??n ?? th? (simple graph). Ng??c l?i l￠ ?a ?? th? (multigraph).
?? th? m￠ m?i c?p ??nh c?a n￳ ??u k? nhau ???c g?i l￠ ?? th? ??y ??. (Complete graph). ??n ?? th? ??y ?? bao g?m n ??nh ???c k hi?u: Kn.
?? th? G' = (V',E') ???c g?i l￠ m?t ?? th? con (subgraph) c?a ?? th? G = (V,E) n?u V' ￌ V; E' ￌ E.
?? th? c￳ s? ??nh v￠ s? c?nh h?u h?n ???c g?i l￠ ?? th? h?u h?n (finite graph), ng??c l?i ???c g?i l￠ ?? th? v￴ h?n (Infinite graph).
Trong gi￡o tr￬nh n￠y, chng ta ch? kh?o s￡t c￡c ?? th? h?u h?n.
2. Bi?u di?n ?? th? TOP


M?t ?? th? c￳ th? ???c bi?u di?n b?ng h￬nh h?c, m?t ma tr?n hay m?t b?ng.
2.1. Bi?u di?n h￬nh h?c
Ng??i ta th??ng bi?u di?n h￬nh h?c c?a ?? th? nh? sau:
- Bi?u di?n m?i ??nh c?a ?? th? b?ng m?t ?i?m (v￲ng tr￲n nh?, ￴ vu￴ng nh?).
- M?t c?nh ???c bi?u di?n b?i m?t ???ng (cong hay th?ng) n?i 2 ??nh li￪n thu?c v?i c?nh ?￳.
V￭ d? 1: ?? th? G c￳: V = {a, b, c, d, e}
E = {ab, ac, ad, bd, cd, ce}
???c bi?u di?n h￬nh h?c nh? sau:

V￭ d? 2: ?? th? G c￳: V = {u, v, x, y}
E = {uv, uv, ux, vx, xy, yy}
???c bi?u di?n h￬nh h?c nh? sau:

Ch : Khi bi?u di?n h￬nh h?c c￡c ?? th?, giao c?a c￡c c?nh ch?a ch?c l￠ ??nh c?a ?? th?.
V￭ d? 3:
V￭ d? 4: C￡c ??n ?? th? ??y ??:

2.2 Bi?u di?n ?? th? b?ng ma tr?n
Ng??i ta c￳ th? bi?u di?n ?? th? b?ng ma tr?n. C￳ 2 ki?u ma tr?n th??ng ???c dng ?? bi?u di?n ?? th?:
- Ma tr?n li￪n k?t hay li?n k? (adjacency matrix).
- Ma tr?n li￪n thu?c (incidence matrix).
￘ Ma tr?n li?n k?
Cho G = (V,E) c￳ n ??nh v1, v2, ., vn. Ma tr?n li?n k? c?a G t??ng ?ng v?i th? t? c￡c ??nh v1, v2, ., vn l￠ m?t ma tr?n vu￴ng c?p n.
A = (aij)n trong ?￳:
aij = 1 n?u vivj l￠ m?t c?nh c?a G.
0 n?u vivj kh￴ng l￠ m?t c?nh c?a G.
￘ Ch :
- Ma tr?n li?n k? c?a m?t ?? th? kh￡c nhau ty thu?c v￠o th? t? li?t k￪ c￡c ??nh. Do ?￳, c￳ t?i n! ma tr?n li?n k? kh￡c nhau c?a m?t ?? th? n ??nh v￬ c￳ n! c￡ch s?p x?p n ??nh.
- Ma tr?n li?n k? c?a m?t ?? th? l￠ m?t ma tr?n ??i x?ng v￬ n?u vi ???c n?i v?i vj th￬ vj c?ng ???c n?i vi v￠ ng??c l?i n?u vi kh￴ng n?i v?i vj th￬ vj c?ng kh￴ng n?i v?i vi.
- M?t v￲ng ???c t￭nh l￠ m?t c?nh t? ??nh v v￠o v.
V￭ d? 5: ?? th? sau: c￳ ma tr?n li?n k? l￠:

V￭ d? 6: H￣y v? ?? th? c￳ ma tr?n li?n k? theo th? t? c?a c￡c ??nh l￠ a, b, c, d.

￘ Ma tr?n li￪n thu?c
Ng??i ta c￲n dng ma tr?n li￪n thu?c ?? bi?u di?n ?? th?. Cho G = (V,E) l￠ m?t ?? th? v?i v1, v2, ., vn l￠ c￡c ??nh v￠ e1, e2, ., em l￠ c￡c c?nh c?a G. Khi ?￳ ma tr?n li￪n thu?c c?a G theo th? t? tr￪n c?a V v￠ E l￠ m?t ma tr?n M = (mij)n x m v?i:
mij = 1 n?u c?nh ej n?i v?i ??nh vi.
0 n?u c?nh ej kh￴ng n?i v?i ??nh vi
￘ Ch : C￡c ma tr?n li￪n thu?c c?ng c￳ th? ???c dng ?? bi?u di?n c￡c c?nh b?i v￠ khuy￪n (v￲ng). C￡c c?nh b?i (song song) ???c bi?u di?n trong ma tr?n li￪n thu?c b?ng c￡ch dng c￡c c?t c￳ c￡c ph?n t? gi?ng h?t nhau v￬ c￡c c?nh n￠y ???c n?i v?i cng m?t c?p c￡c ??nh. C￡c v￲ng ???c bi?u di?n b?ng c￡ch dng m?t c?t v?i ?ng m?t ph?n t? b?ng 1 t??ng ?ng v?i ??nh n?i v?i khuy￪n ?￳.