Chương 1
CÁC KHÁI NIỆM CƠ BẢN CỦA
LÝ THUYẾT ĐỒ THỊ
2
18/02/2011
1.1 Định nghĩa đồ thị
Lý thuyết đồ thị
Định nghĩa 1.
Đơn đồ thị vô hướng G = (V,E) bao gồm Vlà tập các
đỉnh,và Elà tập các cặp không có thứ tự gồm hai phần tử
khác nhau của Vgọi là các cạnh.
Ví dụ
a. Đơn đồ thị vô hướng b. Không phải đơn đồ thị
vô hướng do có các cặp
cạnh nối cùng một cặp
đỉnh
c. Không phải đơn đồ thị
vô hướng do có cạnh nối
một đỉnh với chính nó.
3
18/02/2011
1.1 Định nghĩa đồ thị
Lý thuyết đồ thị
Định nghĩa 2.
Đa đồ thị vô hướng G = (V,E) bao gồm Vlà tập các
đỉnh,và Elà họ các cặp không có thứ tự gồm hai phần tử
khác nhau của Vgọi là các cạnh. Hai cạnh e1và e2được
gọi là cạnh song song nếu chúng cùng tương ứng một cặp
đỉnh.
Ví dụ
Đa đồ thị vô hướng. e1và e2là
các cạnh song song.
e1
e2
4
18/02/2011
1.1 Định nghĩa đồ thị
Lý thuyết đồ thị
Định nghĩa 3.
Giả đồ thị vô hướng G = (V,E) bao gồm Vlà tập các
đỉnh,và Elà họ các cặp không có thứ tự gồm hai phần tử
(không nhất thiết phải khác nhau) của Vgọi là các cạnh.
Cạnh eđược gọi là khuyên nếu nó có dạng e=(u,u).
Ví dụ
Giả đồ thị vô hướng. e
là khuyên
e
5
18/02/2011
1.1 Định nghĩa đồ thị
Lý thuyết đồ thị
Định nghĩa 4.
Đơn đồ thị có hướng G = (V,E) bao gồm Vlà tập các
đỉnh,và Elà tập các cặp có thứ tự gồm hai phần tử khác
nhau của Vgọi là các cung.
Ví dụ
a. Đơn đồ thị có hướng b. Không phải đơn đồ thị
có hướng do có cặp cạnh
nối cùng một cặp đỉnh