TAILIEUCHUNG - GRAPH - Phần 3

Tham khảo tài liệu 'graph - phần 3', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Khoa Công nghệ Thông tin ĐHKHTN. CHƯƠNG III. ĐO THỊ PHANG Định nghĩa a Đồ thì phang - Mồt đồ thì vồ hướng G được goi la phang nếu tồn tai mồt each vẽ G trong mặt phang sao cho khồng cồ hai canh nao cua G cat nhau. - Khi G la một đồ thì phang thì mồi cach vẽ G trong mạt phang sao cho khồng cồ hai canh nao cua G cat nhau được goi la mồt biếu diẽn phang cua G. Ghi chu hai canh cồ chung một đỉnh được qui ước la khồng cat nhau Khong cat nhau Ví du Đồ thì G1 la đồ thì phang va cac đồ thì G2 G3 la cac biếu diẽn phang cua G3 b Phẽp biến đoi đồng phoi Them vao 1 đỉnh nam trẽn 1 canh hay gồp 2 canh cồ chung đỉnh bậc 2 thanh 1 canh. c Đồ thì đồng phoi Hai đồ thì được goi la đồng phoi nếu mồi đồ thì cồ được tư đồ thì kia bang cach thực hiẽn mồt day cac phẽp biến đoi đồng phoi. Đẽ cượng bai giang mồn Ly thuyết đồ thì trang III 1 Khoa Công nghệ Thông tin ĐHKHTN. Đình ly Nếu G là một đồ thị phang thì ta co thể tìm một đổ thị G1 đồng phôi vôi G sao chô cô thế vế G1 bàng càch chỉ dung càc đoan thàng. Ví du Càc đô thị sau đày đông phôi Cac phệp rut gon cơ ban trện đô thị Tính phàng cua môt đô thị không thay đổi nếu thực hiển môt hay nhiểu làn càc phểp rut gọn sau đày à Bô đi càc khuyển b Bô bơt càc canh sông sông chỉ giữ lài môt canh nối hài đỉnh . c Gôp hai canh cô chung đỉnh bàc 2 thành môt canh. Định ly Kuratowski Đình ly 1 Đô thị đu K5 không phàng. Đình ly 2 Đô thị lưỡng phàn đu K3 3 không phàng. K3 3 Để cương bài giang môn Ly thuyết đô thị trang III 2 Khoa Công nghệ Thông tin ĐHKHTN. Nhân xét hai đổ thị K5 và K3 3 là các đồ thị không phang đơn giản nhất vơi các tính chát sau - Néu xồa đi 1 đỉnh hay 1 canh cua 2 đồ thị trén thì chung tá sé cồ được đồ thị phàng. - Đồ thị K5 la đồ thị khồng phang cồ ít đỉnh nhất. - Đồ thị K3 3 la đồ thị khồng phang cồ ít canh nhất. Định ly 3. Điéu kién can va đu đé mồt đồ thị lién thồng G cồ tính phang la G khồng chưa bat ky đồ thị cồn naồ đồng phồi vơi K5 hay K3 3. Ví du. 2 3 5 Đồng phồi Đồ thị cồn 2 3 5 Vé lai 5 7 7 Công

• Kỹ thuật lập trình
• đồ thị
• lý thuyết đồ thị
• nguyên lý đồ thị
• tài liệu về đồ thị
• tự học đồ thị
• cách vẽ đồ thị
• Bài giảng Lý thuyết đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Đồ thị phẳng
• định lý Kemple
• định lý heawood
• đồ thị vô hướng
• đồ thị Euler
• đồ thị hamiton
• bài giảng đồ thị phẳng
• biểu diễn đồ thị
• bậc của đỉnh trong đồ thị
• đại cương đồ thị
• bài giảng về đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• Khái niệm đồ thị
• đồ thị riêng
• sự đẳng hình của đồ thị
• cách biểu diễn đồ thị
• định nghĩa đồ thị
• giáo trình đồ thị
• ứng dụng của đồ thị
• toán rời rạc
• tô màu đồ thị
• Vẽ đồ thị
• bài toán luồng trên mạng
• tài liệu học đại học
• bài giảng toán học
• toán đồ thị
• đơn đồ thị
• đa đồ thị
• giả đồ thị
• đồ thị có hướng