Đường đi Lý_thuyết đồ_thị Đường đi BULLET Cho đồ_thị G X U BULLET Một đường đi trong G là một dãy luân_phiên các đỉnh và cạnh BULLET 1 x u x u x u1 x x là đỉnh và u là cạnh BULLET 2 u x x nếu đồ_thị có hướng BULLET 3 u x x nếu đồ_thị vô hướng BULLET Khi đó ta gọi x là đỉnh đầu và x là đỉnh cuối của đường đi Dây_chuyền BULLET Cho đồ_thị G X U BULLET Một dây_chuyền trong đồ_thị G là một dãy luân_phiên các đỉnh và cạnh BULLET 1 x u x u x u1 x x là đỉnh và u là cạnh BULLET Trong đồ_thị thoả_mãn điều_kiện ui liên_kết với cập đỉnh xi xi 1 không phân_biệt thứ_tự nghĩa_là BULLET 1 u x x hay u x x nếu đồ_thị có hướng BULLET 2 u x x nếu đồ_thị vô hướng BULLET Khi đó ta gọi x là đỉnh đầu và x là đỉnh cuối của dây_chuyền Tính_chất đơn và sơ_cấp của đường đi và dây_chuyền trong đồ_thị BULLET Tính_chất đơn của dây_chuyền hay đường đi yêu_cầu không có cạnh nào xuất_hiện hai lần trong dây_chuyền hay đường đi đó BULLET Tính_chất sơ_cấp hay cũng gọi là thứ cấp yêu_cầu không có đỉnh nào xuất_hiện hai lần Chu_trình và Mạch_BULLET_Một chu_trình trong đồ_thị là một dây_chuyền đơn mà có đỉnh đầu trùng đỉnh cuối tức la dây_chuyền có dạng x u x u x u x u x sao cho các cạnh u_u u đôi một khác nhau BULLET Một_mạch trong đồ_thị là một đường đi đơn mà có đỉnh đầu trùng đỉnh cuối tức_là đường đi có dạng x u x u x u x u x sao cho các cạnh u_u u đôi một khác nhau Dây_chuyền sơ_cấp BULLET Dây_chuyền sơ_cấp là dây_chuyền không có đỉnh lập lại Đường đi sơ_cấp BULLET Đường đi sơ_cấp là đường đi không có đỉnh lập lại Chu_trình sơ_cấp BULLET Chu_trình sơ_cấp là đường đi không có đỉnh lập lại ngoại_trừ đỉnh đầu và đỉnh cuối Mạch sơ_cấp BULLET Mạch sơ_cấp là mạch không có đỉnh lập lại ngoại_trừ đỉnh đầu và đỉnh cuối Ghi_Chú Trong trường_hợp đồ_thị vô hướng thì BULLET Hai khái_niệm dây_chuyền và đường đi là như nhau BULLET Hai khái_niệm chu_trình và mạch là như nhau BULLET Do_đó chúng_ta cũng dùng thuật_ngữ đường đi cho đồ_thị vô hướng đôi_khi một_mạch trong đồ_thị có hướng cũng được gọi là một chu_trình có hướng hay một đường đi trong đồ_thị có hướng cũng được gọi là đường đi có hướng để nhấn_mạnh Khi các cạnh hoàn_toàn được hiểu rõ chẳng_hạn như trong một đồ_thị vô hướng không có cạnh song_song thì BULLET Một dây_chuyền x u x u x u x có_thể viết gọn là x x x x BULLET Một chu_trình x u x u x u x có_thể viết gọn là x x x x Đọc thêm BULLET lý_thuyết đồ_thị BULLET Đồ_thị có hướng BULLET Đồ_thị vô hướng BULLET Thuật_ngữ lý_thuyết đồ_thị BULLET Dây_chuyền Liên_kết ngoài BULLET Sách trực_tuyến về Lý_thuyết đồ_thị BULLET Hướng_dẫn về lý_thuyết đồ_thị BULLET Bài giảng của một môn_học về các thuật_toán đồ_thị BULLET Minh_hoạ hoạt_hình về các thuật_toán đồ_thị BULLET Lần bước thuật_toán để tìm_hiểu BULLET Tóm_tắt các trang minh_hoạ thuật_toán BULLET Dữ_liệu test chuẩn cho các bài_toán đồ_thị con đầy_đủ lớn nhất Maximum_Clique tập con độc_lập lớn nhất Maximum_Independent_Set phủ đỉnh nhỏ nhất Minimum_Vertex_Cover và tô màu đỉnh Vertex_Coloring_BULLET_Sưu tập ảnh số 1 một_số mạng_lưới thực BULLET Sưu_tập ảnh số 1 một_số mạng_lưới thực BULLET Sưu_tập các liên_kết về đồ_thị BULLET Các tạp_chí lý_thuyết đồ_thị BULLET Sách về lý_thuyết đồ_thị
Đường đi ( Lý_thuyết đồ_thị )