intTypePromotion=1

Bài giảng Toán rời rạc (Discrete Mathematics) - Bài 1: Đại cương về đồ thị

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:48

0
53
lượt xem
2
download

Bài giảng Toán rời rạc (Discrete Mathematics) - Bài 1: Đại cương về đồ thị

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Toán rời rạc (Discrete Mathematics) - Bài 1: Đại cương về đồ thị trình bày về đồ thị vô hướng, đồ thị có hướng, biểu diễn đồ thị, đồ thị Euler, Hamilton, đồ thị Hamilton và nửa Hamilton và một số nội dung khác.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Toán rời rạc (Discrete Mathematics) - Bài 1: Đại cương về đồ thị

TRƯỜNG ĐẠI HỌC CẦN THƠ<br /> KHOA CNTT & TRUYỀN THÔNG<br /> BỘ MÔN KHOA HỌC MÁY TÍNH<br /> <br /> 1<br /> <br /> TOÁN RỜI RẠC<br /> <br /> (DISCRETE MATHEMATICS)<br /> 08/2013<br /> <br /> GV: Trần Nguyễn Minh Thư (tnmthu@ctu.edu.vn)<br /> <br /> 2<br /> <br /> ĐẠI CƯƠNG VỀ ĐỒ THỊ<br /> <br /> ĐỒ THỊ VÔ HƯỚNG<br /> 3<br /> <br /> <br /> <br /> G = (X,U), trong đó:<br /> tập hợp các đỉnh<br />  U: tập hợp các cạnh u=(i, j) = (j,i)<br />  Đỉnh kề: chung cạnh (vd đỉnh 1,2)<br />  Cạnh kề: chung đỉnh (vd cạnh u1, u3)<br />  X:<br /> <br /> u5<br /> 4<br /> <br /> 1<br /> u1<br /> <br /> 5<br /> <br /> u6<br /> <br /> Đỉnh cô lập<br /> <br /> u3<br /> 3<br /> <br /> 2<br /> <br /> u10<br /> <br /> 6<br /> Đỉnh treo<br /> <br /> ĐỒ THỊ VÔ HƯỚNG<br /> 4<br /> <br /> <br /> <br /> <br /> <br /> Đa đồ thị: tồn tại cặp đỉnh phân biệt (i,j) có nhiều hơn<br /> một cạnh và không có khuyên<br /> Đồ thị đơn (đơn đồ thị): tất cả các cặp đỉnh (i,j) phân<br /> biệt có nhiều nhất một cạnh và không có khuyên<br /> u4<br /> <br /> u1<br /> <br /> 2<br /> <br /> 4<br /> <br /> u6<br /> <br /> u3<br /> <br /> 1<br /> <br /> u2<br /> <br /> u8<br /> <br /> u5<br /> 3<br /> <br /> u7<br /> <br /> 5<br /> <br /> 6<br /> <br /> ĐỒ THỊ VÔ HƯỚNG<br /> <br /> <br /> <br /> <br /> Đồ thị đầy đủ là đồ thị luôn tồn tại cung/cạnh nối hai<br /> đỉnh bất kỳ<br /> Đồ thị con<br /> tập hợp con của X<br />  Đồ thị con GA của đồ thị G sinh ra bởi A có đỉnh là A có<br /> cung/cạnh là cung/cạnh của G mà đỉnh của chúng thuộc<br /> A.<br />  A là<br /> <br /> 5<br /> <br />
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2